0-1背包问题
有容量为N的背包,M件物品,每件物品只能用一次
每个物品都有自己的质量和重要度
求将不超过背包容量的物品放到背包中,能得到的最大重要度
二维数组:dp[i][j]:在前i件物品中选择一些物品放到容量为j的背包中所获得最大重要度
转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
i:1~M
j:0~n
if(j<v[i])dp[i][j]=dp[i-1][j]
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
解释:在前i件物品中选择一些物品放到容量为j的背包中获得的最大重要度=max(
在前i-1件物品中选择一些物品放到容量为j的背包中获得的最大重要度(第i件不放),
在前i-1件物品中选择一些物品放到容量为j-v[i]的背包中获得的最大重要度+第i件的重要度(第i件放))
二维数组:
dp[j]:将物品放到容量为j的背包中所获的最大重要度
dp[j]=max(dp[j],dp[j-v[i]]+w[i])
i:1~m
j:n~v[i]
dp[j]=max(dp[j],dp[j-v[i]]+w[i])