当前位置: 首页 > article >正文

完全背包模板总结

选或不选

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

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

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

文章目录

    • 选或不选
    • 完全背包(模板,可以配合该视频和我的博客一起看,代码随想录的不推荐看)
    • 完全背包的理解
      • 第一步:回溯法(深度优先遍历)
      • 第二步:改成记忆化搜索
      • 第三步:一比一翻译成动态规划(递推)
      • 优化成一维数组:滚动数组
    • 举例:322.零钱兑换
      • 1.回溯法
      • 2.记忆化搜索
      • 3.动态规划
      • 4.滚动数组

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

image-20241107144115280

完全背包的理解

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

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

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的物品的最大值

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

2.终止条件

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

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

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

3.本层逻辑

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

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

完整代码:

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来写

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,不要忘记

完整代码:

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);
    }
};
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.确定递推公式

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

	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.确定遍历顺序

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

完整代码:

//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];
    }
};
//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背包原理基本相同,只是不能从后往前遍历,而是从前往后遍历,因为要用同一行前面的结果

//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];
    }
};
//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这里就不写了

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的最小金额数

		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

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

完整代码:

当然是超时的

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的那就是算过的,那就直接返回计算过的结果,不需要再次递归了

完整代码:

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

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.滚动数组

把第一维度全都删掉即可

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;
    }
};

http://www.kler.cn/a/383660.html

相关文章:

  • 【day14】异常处理与Object类深入解析
  • [Unity]Unity集成NuGet-连接mysql时的发现
  • Android 常用布局
  • NLP 中文拼写检测开源-01-基于贝叶斯公式的拼写检查器 CSC
  • 20241230 机器学习ML -(1)线性回归(scikitlearn)
  • 入侵他人电脑,实现远程控制(待补充)
  • 设计者模式之策略模式
  • 《构建一个具备从后端数据库获取数据并再前端显示的内容页面:前后端实现解析》
  • 集中管理用户名和密码,定期修改密码快捷方便
  • 参数跟丢了之JS生成器和包装器
  • PostgreSQL核心揭秘(三)-元组结构
  • 【科普】conda、virtualenv, venv分别是什么?它们之间有什么区别?
  • 讲讲RabbitMQ 性能优化
  • Qt中弹出窗口的实现与鼠标事件处理
  • ctfshow(91,96,97)--PHP特性
  • Spring Boot 中Nacos的用法及流程
  • lua入门教程 :模块和包
  • 【C++】vector 类深度解析:探索动态数组的奥秘
  • Hive面试题-- hive中查询用户连续三天登录记录的实现与解析
  • 【码农日常】Vscode Clangd初始化失败(Win10)
  • M1M2 MAC安装windows11 虚拟机的全过程
  • CSS中常见的两列布局、三列布局、百分比和多行多列布局!
  • 13.React useTimeout
  • 服务器虚拟化:现代IT基础设施的基石
  • 【660】基于SSM+Vue的在线学习系统设计与实现
  • 数据库_SQLite3