AKSZ-背包

sxq

2024-06-30 17:41:55

发布于：广东

1阅读

0回复

0点赞

背包入门

0/1背包模型

有一个容量V的背包，在K个物品中选择一些物品装入，每个物品只有装/不装两个状态，
怎样能保证所撰的物品价值最大；

思路

设dp[i][j]表示前i个物品已经选好了最佳方案，且容量不超j，所能获取的最大值
对于第i个物品
选择不装，则的dp[i][j]=dp[i-1][j] (不装不影响所装的价值)
选择装，则dp[i][j]=dp[i-1][j-v[i]]+w[i];（拿一个物品，占用对应空间，加上对应价值）
所以两者取最大 dp[i][j]=max(dp[i][j]=dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
初始化dp[0][V]=0;
答案：dp[K][V];