【动态规划 | 完全背包】动态规划经典应用：完全背包问题详解

完全背包问题是动态规划的经典应用，相比01背包，物品可以无限选取，解法更具技巧性。本文将详解完全背包的状态转移方程，分析空间优化方法，并通过实例演示如何高效求解，帮助读者快速掌握这一重要算法模型。

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅

【模板】完全背包

【题目】：【模板】完全背包

【背包至多容量:算法思路】 (紫色字体为思路)

完全背包跟01背包区别在于，物品可以多次进行选择。根据"经验 + 题目要求"快速得到我们的状态转移方程，对最后一个位置进行分情况讨论，物品有多种情况分析，这里通过数学方式简化该过程。需要注意j >= v[i]。

【初始化】

这里只需初始化第一行。在循环中完成第一类的初始化，并且不会发生越界问题，因为 j >= nums[i] 时会使用 i-1 位置的元素，而不会访问右侧越界的数据。

【代码实现】

#include <iostream>
#include<string.h>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];

int main()
{
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    //1.解决第一问
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
                if(j >= v[i])
                    dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

【细节问题】

牛客网属于ACM模式需要整体实现，对此一般定义全局变量，默认数值尾0，无需特殊的初始化。

【背包恰好装满:算法思路】 (绿色字体为思路)

状态定义：dp[i][j] 表示前 i 个物品中，总体积为 j 的最大价值。

状态转移：dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])，但要确保 dp[i][j-v[i]] != -1，即该状态合法。

初始化：

• dp[0][0] = 0（体积为0时价值为0）。
• dp[0][j] = -1（没有物品时无法填充体积 > 0）。

填表：按状态转移方程从上到下填表。

返回结果：最后需要判断是否能凑成体积为 V，若不能则返回 -1

【代码实现】

 memset(dp, 0, sizeof dp);
    for(int j = 1; j <= V; j++) dp[0][j] = -1;
    //2.解决第二问
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
                if(j >= v[i] && dp[i][j - v[i]] != -1)
                    dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }
    cout << ( dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}

【优化方案】

这里的优化方案与 01 背包问题相似，都是通过滚动数组进行优化，主要的区别在于遍历方向。具体来说，01 背包问题需要使用当前行未修改的数值，因此遍历方向是从右往左；而完全背包问题则需要使用当前行已修改的数值，因此遍历方向是从左往右。理解这一点就足够了，没必要过于纠结细节，避免增加学习成本。

• 01背包：使用滚动数组优化时，从右到左遍历是正确的。因为每个物品只能使用一次，在更新 dp 数组时，我们不希望当前物品对同一行之前的 dp 值产生影响。因此，遍历方向应从右往左，保证当前物品在更新时不覆盖还未处理的 dp 值。
• 完全背包：同样使用滚动数组优化时，从左到右遍历也是正确的。因为每个物品可以使用多次，所以我们需要确保当前物品的多次使用能够影响到同一行的后续 dp 值，因此遍历方向从左往右。

【代码优化】

if(dp[j - v[i]] != -1)才进行max函数比较，避免w[i]影响数值。对此完全背包这里可以设置dp[j] = -0x3f3f3f3f，就算进行比较也不会影响最终结果

#include <iostream>
#include<string.h>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N];

int main()
{
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    //1.解决第一问
    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= V; j++)
        {
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;

    memset(dp, 0, sizeof dp);
    for(int j = 1; j <= V; j++) dp[j] = -0x3f3f3f3f;
    //2.解决第二问
    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= V; j++)
        {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << ( dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}

322. 零钱兑换

【题目】：322. 零钱兑换

【算法思路】

根据"经验 + 题目分析"可知，在物品无限的情况下，背包容量表示总金额，最少硬币个数为需求，这可以通过“完全背包”问题来解决。

我们可以通过分析最终状态来优化解法，结合数学公式来减少不必要的计算。在初始化时，像01背包一样，需要判断当前状态是否存在，通常使用 -1 来标记不存在的状态。

【代码实现】

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) 
    {
        //1.创建dp表
        int n = coins.size();
        vector<vector<int>> dp(n + 1,vector<int>(amount + 1));

        //2.初始化
        for(int j = 1; j <= amount; j++) dp[0][j] = INF;

        //3.填表操作
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                    if(j >= coins[i - 1])
                         dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }

        //3.返回值
        return dp[n][amount] >= INF ? - 1 : dp[n][amount];
    }
};

【优化方案】

注意完全背包和01背包遍历方向不同即可，其他优化方案几乎是相同的。

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) 
    {
        //1.创建dp表
        int n = coins.size();
        vector<int> dp(amount + 1);

        //2.初始化
        for(int j = 1; j <= amount; j++) dp[j] = INF;

        //3.填表操作
        for(int i = 1; i <= n; i++)
        {
            for(int j = coins[i - 1]; j <= amount; j++)
            {
                dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }

        //3.返回值
        return dp[amount] >= INF ? - 1 : dp[amount];
    }
};

该优化方案不适用于01背包，因为01背包要求每个物品只能使用一次，因此必须从右往左遍历，以确保未使用的数值不被重复计算。因此，需要使用 if 语句来确保安全性，确保未使用的物品不会被重复计算。

518. 零钱兑换 II

【题目】：518. 零钱兑换 II

【算法思路】

如果确定这是一个背包问题，可以根据状态表示模板，并结合题意进行调整，从而得到适合该问题的状态表示。

【代码实现】

class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        vector<long> dp(amount + 1);
        dp[0] = 1;
        for(auto x : coins)
            for(long j = x; j <= amount; j++)
                dp[j] += dp[j - x];
                
        return dp[amount];
    }
};

279. 完全平方数

【题目】：279. 完全平方数

【算法思路】

通过“经验 + 题目分析”，我们可以推导出状态转移方程。由于 i^2 ≤ n，因此 i 的取值范围最多到 √n，所以行数可以设为 √n。接着，通过分析最终状态，并结合数学推导，得到状态转移方程。

【代码实现】

class Solution {
public:
    int numSquares(int n) 
    {
        int m = sqrt(n);
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int j = 1; j <= n; j++) dp[0][j] = INF;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                    if(j >= i * i)
                        dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        }

        return dp[m][n];
    }
};

【优化方案】

class Solution {
public:
    int numSquares(int n) 
    {
        int m = sqrt(n);
        const int INF = 0x3f3f3f3f;
        vector<int> dp (n + 1, INF);
        dp[0] = 0;
        for(int i = 1; i <= m; i++)
            for(int j = i * i; j <= n; j++)
                dp[j] = min(dp[j], dp[j - i * i] + 1);

        return dp[n];
    }
};

快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！