动态规划——01背包、完全背包（python，二维DP）

01背包（二维DP）

思路：

m种物品，背包容量为n，物品重量数组v，物品价值数组price。

dp=[[0]*(n+1) for _ in range(m+1)] for i in range(1,m+1): for j in range(1,n+1): if j <v[i-1]: dp[i][j]=dp[i-1][j] else: dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+price[i-1]) print(dp[m][n])

完全背包（二维DP）

关键：dp[][]=max(dp[i-1][j],dp[i][j-v[i-1]]+price[i-1])

dp=[[0]*(n+1) for _ in range(m+1)] for i in range(1,m+1): for j in range(1,n+1): if j<v[i-1]: dp[i][j]=dp[i-1][j] else: dp[i][j]=max(dp[i-1][j],dp[i][j-v[i-1]]+price[i-1]) print(dp[m][n])