【C++】算法集锦(9):背包问题
发布日期:2021-06-30 19:47:33
浏览次数:2
分类:技术文章
本文共 2256 字,大约阅读时间需要 7 分钟。
文章目录
本来要拿《背包九讲》作为参考的,奈何太抽象,我看不懂
0-1背包问题
给你一个载重量为 W 的背包,以及一堆物品,这些物品都有属于自己的两个属性:价值var和质量wt,试问这个背包最多能装多少价值的物品。
这里面的每一个物品,要么装,要么不装。
看到这个图,第一反应是不是:性价比比一下。如果是这样想的朋友可以停下来了,性价比不行。
如果只有两个物品,一个4Kg,值8¥;一个15Kg,值10¥;很明显前面那个性价比高,但是显然我们要选的是后面这个。这种题目,实在让人很懵逼,就好像千头万绪,但是所有思路都被自己给否定了。
动态规划标准套路
1、明确状态和选择
什么是状态,就是背包的容量,以及可以选择的物体。 什么是选择,这个物品,要不要放进背包。2、明确dp数组
刚刚说到有两个状态,所以我们选用一个二维数组:dp[i][w]:对于前 i 个物体,在背包容量为w的时候,可以装的最大价值是dp[i][w]。 例:dp[3][5] = 6:对于前三个物体做选择,在背包容量为5的时候,可以选择的最大价值为6。根据定义,我们的最终目标可以设为 dp[N][M],
base case 就是dp[0][···] = 0,dp[···][0] = 0,没有物品或者背包没有空间的时候,能装的最大价值就是0。3、状态转移方程
对第i件物品来说,无非就是选中了,和没选中嘛。 那么,如果选中了:d[i][w] = d[i-1][w-wt[i-1]]+var[i]如果没选中:d[i][w] = d[i-1][w]
什么情况下要选?什么情况下不选呢?
那当然是哪个有利就选哪个嘛。所以,伪代码怎么写?
伪代码
int dp[N+1][W+1]dp[0][···] = 0dp[···][0] = 0for i in range(1,N): for w in range(1,w): dp[i][w] = max(装,不装) //装不装的状态转移已经在上面了return dp[N][W]
修缮代码
int knaspsack(int W,int N,vector & wt,vector & val){ vector> dp(N+1,vector (W+1,0)); for(int i = 1;i <= N; i++){ for(int w = 1;w <= W; w++){ if(w-wt[i-1]<0) //没空间了 dp[i][w] = dp[i-1][w]; else dp[i][w] = max(d[i-1][w-wt[i-1]]+var[i],dp[i-1][w]); } } return dp[N][W];}
子集背包问题
给你一个只包含正整数的数组,设计一个算法,将这个数组分为两个元素和相等的子集,如果能分,返回true,如果不能分,返回false。
这个问题怎么转化为背包为题呢?首先,对这个数组计数,如果和是奇数,就返回-1吧,如果和是偶数,就除于二,记为n。
这个问题就转变为:从数组中找出一些数,使得它们的和恰好等于n。其实看了这个题目,最直接的想法就是逆序排序之后用回溯
思路分析
状态和选择已经很明确了吧。
dp数组的含义嘛,dp[i][j] = x 表示,对于前 i 个物品,当前背包容量为 j 的时候,正好能将背包装满,则x为true,否则为false、 做一下状态压缩,把[i]去掉,反正i也是用来循环的。如果不把 nums[i] 装入子集,则能够恰好装满背包,取决于上一个状态 dp[i-1][j],继承之前的结果。
如果把 nums[i] 装入子集,则能否恰好装满背包,取决于状态 dp[i-1][j-nums[i-1]]。代码实现
bool canPartition(vector & nums) { int sum = 0, n = nums.size(); for (int num : nums) sum += num; if (sum % 2 != 0) return false; sum = sum / 2; vectordp(sum + 1, false); // base case dp[0] = true; for (int i = 0; i < n; i++) for (int j = sum; j >= 0; j--) if (j - nums[i] >= 0) dp[j] = dp[j] || dp[j - nums[i]]; return dp[sum];}
完全背包问题
换零钱问题:给定不同面额的硬币(coins),和一个总金额(amount),写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无数个。
说真的,我都快受不了了,是回溯不好用了吗?
来我画个图:
比方说现在,有1、2、5三种面值的硬币,总目标为10吧。是吧,是回溯吧,这个我画的决策树可能是丑了点(我看得出来),将就着理解一下吧。
转载地址:https://lion-wu.blog.csdn.net/article/details/113994053 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月13日 16时16分58秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
油猴脚本:微信推送浏览功能拓展
2019-04-30
JavaScript DOM对象操作详解
2019-04-30
JavaScript 表单操作与MD5加密
2019-04-30
JAVA学习笔记4 - 循环与分支结构
2019-04-30
JAVA学习笔记6 - 数组
2019-04-30
JAVA学习笔记8 - Stream 和 File I/O
2019-04-30
JAVA学习笔记9 - 异常
2019-04-30
JAVA学习笔记10 - 继承
2019-04-30
JAVA学习笔记11 - 接口interface
2019-04-30
JAVA学习笔记12 - 包package
2019-04-30
Android 开发学习笔记 00 - Getting Started
2019-04-30
【学习笔记】Android Activity
2019-04-30
【学习笔记】Android Fragments
2019-04-30
Android使用Retrofit_00_Getting Started
2019-04-30
Android使用Retrofit_01_OAuth2 + GitHub
2019-04-30
Django + REST学习笔记
2019-04-30