- 完全背包问题 -

张开发
• 2026/4/16 13:56:07 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

- 完全背包问题 -
完全背包问题定义有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i]。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。注意 完全背包问题 和 01背包问题唯一不同的地方就是每种物品有无限件题解定义dp数组dp[i][j]:i表示 从0-i 序号的物品选择j表示此时背包的容纳重量数组的值表示该条件下的背包里物品的最大价值递推表达式依旧分为两种情况对于dp[i][j]:不放物品i: 背包容量为j 那么背包不放物品i的最大价值为dp[i-1][j]放物品i: 背包空出物品i后还剩j - weight[i]的容量此时与 01背包问题不同由于物品可以重复放入所以对于剩余j - weight[i]容量仍然可以放入物品i 因此此时最大价值为dp[i][j-weight[i]] value[i]。不同于01背包的dp[i-1][j-weight[i]] - value[i]因此递推公式为dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i])初始化因为递归表达式同时与i行 和i - 1行相关因此需要初始化dp[0][...]以及dp[...][0]。对于dp[0][...]:当j weight[0]时: 容量不够放因此dp[0][j] 0当j weight[0]时:dp[0][j]如果能放下weight[0]的话就一直装每一种物品有无限个对于dp[...][0]: 因为背包容量为0所以初始值为0初始化代码// 初始化 因为dp数组默认为0所以对于 dp[...][0] 不用刻意 去初始化for(intjweight[0];jbagWeight;j){dp[0][j]dp[0][j-weight[0]]value[0];}遍历顺序先遍历物品和先遍历背包都可以便于理解先遍历物品 即从左到右 从上到下问题变形

更多文章