关于完全背包的解析以及完全背包与01背包的区别及代码-Toy模板网

这篇具有很好参考价值的文章主要介绍了关于完全背包的解析以及完全背包与01背包的区别及代码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

完全背包是什么呢？如果大家了解过01背包那么完全背包也是可以理解的。完全背包也是求一个固定容量的背包，能够装入物品的最大价值是多少，也就是说该背包最多能装多少价值？和01背包不同的是，完全背包里所能装的各个物品给定是无限的，也就是说同一个物品我们可以取很多次。

这就是它们的题目区别，这一点区别对于遍历顺序来说影响巨大，我们这次用一维数组来解决完全背包的问题。

关于一维数组解决思路如果有不明白的地方，可以去看我以前发过的01背包的一维数组解决思路。

完全背包一维数组解决的动规五部曲中，dp数组的含义，递推公式，dp数组的初始化与01背包的一维数组解决思路前三步完全相同，这里不再做过多描述。我们重点讲解完全背包的遍历顺序是怎样的。

完全背包的遍历顺序，对于背包遍历顺序不再和01背包相同了，01背包的遍历顺序是从后向前，这是由于我们递推公式特性决定的，它会和之前的容量价值相对比，为了使背包中每个物品都只能用一次，所以我们只能用倒序的遍历，而完全背包物品可以用无数次，所以我们要遍历背包时候，正序遍历。这样第一次遍历其他容量的背包就有数，大容量背包在第一次填数时候就可以和之前小容量背包比较价值，使背包加入更多同样物品，进而使背包价值更大。这里的背包遍历顺序是由物品的数目不同而引起的变化。

那么完全背包的两层fou循环可以颠倒吗？也就是说我们可以先遍历背包再遍历物品吗？答案是纯完全背包的问题是可以的！两个for循环颠倒顺序没有什么影响。没错，即使是用一维数组实现完全背包，它仍然不受影响，完全背包的各部分数据也就是背包价值，是由上一次的填数所推出的，即使先锁定背包容量，往里面持续填各种物品也是可以的，因为物品数目没有限制的缘故，并不会发生类似于01背包锁定背包容量时，出现的背包只能装入一个物品的bug！锁定背包容量，也就是背包容量遍历在第一个for循环，也就是外部循环，它遍历完之后并不会再遍历了，如果是01背包由于它的背包遍历还是倒着遍历的，以至于在放后面的物品时候，根据递推公式我们要腾出地方dp【j-weight【i】】这个时候前面的小容量背包暂时没有值，导致背包虽有空间但却无法放入其他物品！！！这也是为什么01背包不能够颠倒for循环，可能以前的那个章节我对这里的解释并不是很清晰，大家可以看这里好好理解。01背包之所以不能够颠倒for循环，和递推公式、物品的数量限制、01背包的本身遍历背包的顺序是有着不可分割的关系的。

我们上面提到了，下一步我们要填的数是和上一次的值推出来的，我们可以分别画表格，无论是哪一个先遍历，都不会影响完全背包的背包价值，因为它是正向遍历背包且物品可以放很多个，这样在放其他物品时候和上一次放很多个上一个物品时候，取最大值是不受for循环颠倒所干扰的。

实际上这些事情在我第一次学习01背包的时候并不能很好的理解，为什么01背包用一维数组实现不能for循环倒置，那个时候还有想过，如果倒置了之后背包不倒序遍历呢？其实和这个没有干系，背包的倒序遍历，是控制物品个数的！我们要搞清楚哪一步都是用来做什么的，这样才能更深刻的理解解题思路。理论的解释可能有时候显得确实差一点意思，感觉不到到底是究竟为什么完全背包就不受for循环颠倒所影响，最好还是通过对代码的调试来理解，到底是否存在着干扰。

给出代码文章来源地址https://www.toymoban.com/news/detail-408316.html

// 先遍历物品，在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}


// 先遍历背包，再遍历物品
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    vector<int> dp(bagWeight + 1, 0);

    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

到了这里，关于关于完全背包的解析以及完全背包与01背包的区别及代码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！