完全背包模板

选或不选

0-1背包 完全背包_哔哩哔哩_bilibili

动态规划应该如何学习？-CSDN博客

01背包模板 | 学习总结-CSDN博客

完全背包（模板，可以配合该视频和我的博客一起看，代码随想录的不推荐看）

image-20241107144115280

完全背包的理解

1.首先要知道dfs/dp含义是在前i个物品容量为c的情况下能选出来的最大价值

2.其实就是把递推公式里面的

1
dfs(w,v,i-1,c-w[i])+v[i]改为dfs(w,v,i,c-w[i])+v[i]

原来是第i个物品选或者不选

现在是轮到第i个物品的时候尽可能的多拿

3.有人可能疑惑这样能不能选出来最大值

其实它每次选都会和没有选第i个物品容量为c的dp[i-1][c]进行比较，只有dp[i][c-w[i]]+w[i]大的时候才会更新

4.01背包中我们第i个物品的两个选择全都来自i-1时候（正上方和左上方）

现在一个是i-1一个是i（正上方和同一行左方）

所以遍历的时候只能从前往后不可以从后往前，因为后面的结果要依赖前面的结果

5.由i-1到i为什么能够代表第i个无限拿？

我们传入的i的含义是第i个元素拿不拿

不拿就是：dfs(w,v,i-1,c)

拿了就是：dfs(w,v,i,c-w[i])+v[i]

如果我们这层递归函数里面拿了，我们在往下递归的时候，传入的还是i，也就是说继续看i能不能拿

第一步：回溯法（深度优先遍历）

思路：

配合视频一起看更棒

0-1背包 完全背包_哔哩哔哩_bilibili

这个虽然过不了，时间复杂度太高，但是这是学习动态规划的必由之路

1.返回值和参数

w各个物品所占空间

v各个物品价值

对第i个物品进行选择

c是当前剩余的容量

返回值返回选或不选编号为i的物品的最大值

1
int dfs(vector<int>& w,vector<int>& v,int i,int c)

2.终止条件

1
2
3
4
if(i<0)
	return 0;
if(c<w[i])
	return dfs(w,v,i-1,c);

如果编号小于0说明已经到了树形结构最下面了，要开始从第一个物品选了，即自底（第一个物品）向上（i依次增大）开始遍历

如果当前容量已经小于要选的物品，那就直接返回给上层不选i号物品的结果

3.本层逻辑

在选和不选当前物品两种情况中（只要返回回来的一定是最大值），挑一个更大的返回

1
return max(dfs(w,v,i-1,c),dfs(w,v,i,c-w[i])+v[i]);

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int dfs(vector<int>& w,vector<int>& v,int i,int c)
    {
        if(i<0)
			return 0;
        if(c<w[i])
            return dfs(w,v,i-1,c);
        return max(dfs(w,v,i-1,c),dfs(w,v,i,c-w[i])+v[i]);
    }
    int Completeknapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        return dfs(w,v,nums.size()-1,c);
    }
};

C++还可用lambda来写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int Completeknapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        function<int(int,int)> dfs=[&](int i,int c)->int{
            if(i<0)
                return 0;
            if(c<w[i])
                return dfs(i-1,c);
            return max(dfs(i-1,c),dfs(i,c-w[i])+v[i]);
        };
        return dfs(nums.size()-1,c);
    }
};

第二步：改成记忆化搜索

注意，在递归函数中，我们同时有物品编号i和容量c，所以要用一个二维数组作为哈希表来存储计算结果进行复用。

然后在每次返回结果前都赋值一下，把计算结果给存储起来

容量的大小为c，vector初始化要为c+1，不要忘记

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
	int dfs(vector<int>& w,vector<int>& v,int i,int c,vector<vector<int>>& dp)
    {
        if(i<0)
            return 0;
        if(dp[i][c]!=-1)
            return dp[i][c];
        if(c<w[i])
            return dp[i][c]=dfs(w,v,i-1,c,dp);
        return dp[i][c]=max(dfs(w,v,i-1,c,dp),dfs(w,v,i,c-w[i],dp)+v[i]);
    }
    int Completeknapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<vector<int>> dp(nums.size(),vector<int>(c+1,-1));
        return dfs(w,v,nums.size()-1,c,dp);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int 01knapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<vector<int>> dp(nums.size(),vector<int>(c+1,-1));
        function<int(int,int)> dfs=[&](int i,int c)->int{
            if(i<0)
            return 0;
            if(dp[i][c]!=-1)
                return dp[i][c];
            if(c<w[i])
                return dp[i][c]=dfs(i-1,c);
            return dp[i][c]=max(dfs(i-1,c),dfs(i,c-w[i])+v[i]);
        };
        return dfs(nums.size()-1,c);
    }
};

第三步：一比一翻译成动态规划(递推)

1.确定dp数组以及下标的含义

二维数组，dp[i][c]就是在前i个物品里面选在最大容量为c时可以取到的最大价值

i是物品编号，对于i的物品做出选择

c是当前背包的总容量

2.确定递推公式

1
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

3.dp数组如何初始化

这里有两个版本

1.dp数组中物品编号从1开始

这个只需要把dp初始化为0即可

这里要注意w和v中如果没有统一物品编号从1开始的话，下面递推公式里面就会是i-1

2.dp数组中物品编号从0开始

这个由于要避免i-1的数组越界，需要对i==0的情况进行初始化，就是各个容量下可以放多少个物品0

1
2
3
4
5
6
vector<vector<int>> dp(n+1,vector<int>(c+1,0));
   for (int j = 0; j <= c; ++j) {
       if (j >= w[0]) {
           dp[0][j] = v[0] * (j / w[0]);
       }
   }

4.确定遍历顺序

因为要用到正上方和同一行左方的数据，所以最好先遍历物品在遍历容量再从前往后遍历

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//dp数组中的物品编号从1开始
class Solution {
public:
    int 01knapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<vector<int>> dp(nums.size()+1,vector<int>(c+1,0));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=c;j++)
                if(j<w[i-1])//i-1是因为在w和v中物品编号从0开始的
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);
        }
        return dp[w.size()][c];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//dp数组中的物品编号从0开始
class Solution {
public:
    int 01knapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<vector<int>> dp(nums.size(),vector<int>(c+1,0));
        for (int j = 0; j <= c; ++j) {
            if (j >= w[0]) {
                dp[0][j] = v[0] * (j / w[0]);
            }
        }
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=c;j++)
                if(j<w[i])
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
        }
        return dp[w.size()-1][c];
    }
};

优化成一维数组：滚动数组

与01背包原理基本相同，只是不能从后往前遍历，而是从前往后遍历，因为要用同一行前面的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//dp数组中的物品编号从0开始
class Solution {
public:
    int 01knapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<int> dp(c+1,0);
        for(int i=0;i<n;i++)
        {
            for(int j=w[i];j<=c;j++)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
        return dp[c];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//dp数组中的物品编号从1开始
class Solution {
public:
    int 01knapsack(vector<int>& nums,int c) {
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<int> dp(c+1,0);
        for(int i=1;i<=n;i++)
        {
            for(int j=w[i-1];j<=c;j++)
                dp[j]=max(dp[j],dp[j-w[i-1]]+v[i-1]);
        }
        return dp[c];
    }
};

可以看到一维的就没啥区别了，因为从0和从1开始都只是dp数组里面存储的位置往后挪了一位而已

举例：322.零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

套用模板时候的注意点

1.这道题的金币可以重复选，所以是完全背包不是01背包

2.这道题是返回最少的金币数量，所以dfs/dp的含义就是前i种金币可以凑成金额为c的面额的最少金币数量是多少

3.由于求的是金币数量，所以面额amount就是背包的容量，物品的重量就是自己的面额，每个物品的价值都为1，因为dfs和dp的含义是最少的金币的数量是多少

4.求的是最少，所以要把max换成min，初始化的时候要初始化为INT_MAX/2而不是0（除以2是因为返回的INT_MAX+1后会溢出，导致报错）

1.回溯法

1.参数和返回值

i是物品编号，表示从前i个物品里面选

c是容量

coins是w[i]

v[i]的值全都为1这里就不写了

1
int dfs(int i,int c,vector<int>& coins)

2.终止条件

i小于0说明到了树形结构的最下面了

如果同时容量c==0，那说明正好可以凑够，我们就找到了一个合法的方案，返回0（不返回1的原因是我们dfs的含义是最少金币的数量，而不是能凑够amount的方案数量）

如果容量不是0就凑不够，返回INT_MAX/2

如果容量不够当前的硬币，那就递归下一个物品去了，最后返回的就是在前i-1种金币能凑够amount的最小金额数

1
2
3
4
5
6
7
if(i<0)
          if(c==0)
              return 0;
          else
              return INT_MAX/2;
      if(c<coins[i])
          return dfs(i-1,c,coins);

3.本层逻辑

递归公式max换成min

1
return min(dfs(i-1,c,coins),dfs(i,c-coins[i],coins)+1);

完整代码：

当然是超时的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int dfs(int i,int c,vector<int>& coins)
    {
        if(i<0)
            if(c==0)
                return 0;
            else
                return INT_MAX/2;
        if(c<coins[i])
            return dfs(i-1,c,coins);
        return min(dfs(i-1,c,coins),dfs(i,c-coins[i],coins)+1);
    }
    int coinChange(vector<int>& coins, int amount) {
        int res=dfs(coins.size()-1,amount,coins);
        if(res<INT_MAX/2)
            return res;
        else
            return -1;
    }
};

2.记忆化搜索

就是还是全都初始化为-1，每次返回前给dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int dfs(int i,int c,vector<int>& coins,vector<vector<int>>& dp)
    {
        if(i<0)
            if(c==0)
                return 0;
            else
                return INT_MAX/2;
        if(dp[i][c]!=-1)
            return dp[i][c];
        if(c<coins[i])
            return dp[i][c]=dfs(i-1,c,coins,dp);
        return dp[i][c]=min(dfs(i-1,c,coins,dp),dfs(i,c-coins[i],coins,dp)+1);
    }
    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>> dp(coins.size(),vector<int>(amount+1,-1));
        int res=dfs(coins.size()-1,amount,coins,dp);
        if(res<INT_MAX/2)
            return res;
        else
            return -1;
    }
};

3.动态规划

笔者选择的是dp数组的物品编号从1开始

递归的边界条件是

i<0的时候c==0是返回0的。而我们这里的dp数组编号从1开始，那就是i<1且c==0的时候是等于0的

所以dp[0][0]的初始值就为0，其他的都是INT_MAX/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>> dp(coins.size()+1,vector<int>(amount+1,INT_MAX/2));
        dp[0][0]=0;
        for(int i=1;i<=coins.size();i++)
            for(int j=0;j<=amount;j++)
                if(j<coins[i-1])
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
        if(dp[coins.size()][amount]<INT_MAX/2)
            return dp[coins.size()][amount];
        else
            return -1;
    }
};

4.滚动数组

把第一维度全都删掉即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX/2);
        dp[0]=0;
        for(int i=1;i<=coins.size();i++)
            for(int j=coins[i-1];j<=amount;j++)
                dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
        if(dp[amount]<INT_MAX/2)
            return dp[amount];
        else
            return -1;
    }
};