写一个简单的动态规划demo

好的，这里提供一个简单的动态规划demo：

问题描述：有n件物品和一个容量为m的背包，每件物品有自己的重量和价值，在该限制下背包能够装入的最大价值是多少？

解决方案：动态规划算法

代码实现：

def knapsack(n, m, w, v):
    '''
    n: 物品个数 
    m: 背包容量 
    w: 物品重量列表 
    v: 物品价值列表 
    '''
    # 初始化二维数组，行为物品个数，列为背包容量 
    dp = [[0 for j in range(m+1)] for i in range(n+1)]
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 当前物品超过背包容量则不放入 
            if w[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                # 选择放或者不放当前物品 
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
    
    # 返回最终结果 
    return dp[n][m]
    
# 示例 
print(knapsack(3, 5, [2, 1, 3], [4, 2, 3]))

以上代码实现的是 0-1 背包问题，运用了动态规划思想进行解决，算法时间复杂度为 O(nm)。