代码随想录Day37 动态规划：完全背包理论基础，518.零钱兑换II，本周小结动
1.完全背包理论基础思路
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight，得到的价值是value 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
背包最大重量为4。
物品为：
重量价值物品0115物品1320物品2430 每件商品都有无限个！
问背包能背的物品最大价值是多少？
01背包和完全背包唯一不同就是体现在遍历次序上，以是本文就不去做动规五部曲了，我们直接针对遍历次序经行分析！
关于01背包我如下两篇已经举行深入分析了：
[*]动态规划：关于01背包问题，你该相识这些！(opens new window)
[*]动态规划：关于01背包问题，你该相识这些！（滚动数组）
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，以是要从小到大去遍历
在动态规划：关于01背包问题，你该相识这些！（滚动数组） (opens new window)中也做了讲解。
dp状态图如下：
https://i-blog.csdnimg.cn/img_convert/4fb4d12d557a6fd252c30368c26318c7.jpeg
相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。
其实还有一个很紧张的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该云云一样，那么为什么呢？
难道就不能遍历背包容量在外层，遍历物品在内层？
看过这两篇的话：
[*]动态规划：关于01背包问题，你该相识这些！(opens new window)
[*]动态规划：关于01背包问题，你该相识这些！（滚动数组）(opens new window)
就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套次序是无所谓的！
因为dp 是根据 下标j之前所对应的dp盘算出来的。 只要保证下标j之前的dp都是颠末盘算的就可以了。
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
https://i-blog.csdnimg.cn/img_convert/b9705919e386a054b742d3b8294f55e6.jpeg
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
https://i-blog.csdnimg.cn/img_convert/95ef09b368ec6d22a8286016d1002728.png
看了这两个图，大家就会明白，完全背包中，两个for循环的先后循序，都不影响盘算dp所需要的值（这个值就是下标j之前所对应的dp）。
总结
对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
先遍历物品，再遍历背包
public class Complete_Knapsack_Problem {
//先遍历物品，再遍历背包
private static void testCompletePack(){
int[] weight = {1, 3, 4};//定义了三种物品，它们的重量分别是1、3、4，对应的价值分别是15、20、30。
int[] value = {15, 20, 30};
int bagWeight = 4;//背包的总容量是4。
int[] dp = new int;//dp数组用于存储每个容量下的最大价值。数组的大小是背包容量加1，因为容量从0开始。
for (int i = 0; i < weight.length; i++){//外层循环遍历所有物品，内层循环遍历所有可能的背包容量。对于每个物品i和每个容量j，我们考虑两种情况：不取当前物品，那么当前容量下的最大价值仍然是dp。取当前物品，那么当前容量下的最大价值是dp] + value，即取走当前物品后剩余容量下的最大价值加上当前物品的价值。
for (int j = weight; j <= bagWeight; j++){
dp = Math.max(dp, dp] + value);//比较了这两种情况，取两者的最大值作为当前容量下的最大价值。
}
}
for (int maxValue : dp){//遍历dp数组，输出每个容量下的最大价值。
System.out.println(maxValue + " ");
}
}
}
[*]时间复杂度：两种方法的时间复杂度都是
页:
[1]