主要参考：
一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现）
https://blog.csdn.net/qq_33098049/article/details/81562893
背包问题是动态规划非常重要的一类问题，它有很多变种，但题目千变万化都离不开我根据力扣上背包问题的题解总结的解题模板。负责任地说，吃透这一篇文章，力扣上所有背包问题拿过来就可以秒杀！
背包定义：那么什么样的问题可以被称作为背包问题？换言之，我们拿到题目如何透过题目的不同包装形式看到里面背包问题的不变内核呢？
我对背包问题定义的理解：
给定一个背包容量target，再给定一个数组nums(物品)，能否按一定方式选取nums中的元素得到target
注意：
1、背包容量target和物品nums的类型可能是数，也可能是字符串
2、target可能题目已经给出(显式)，也可能是需要我们从题目的信息中挖掘出来(非显式)(常见的非显式target比如sum/2等)
3、选取方式有常见的一下几种：每个元素选一次/每个元素选多次/选元素进行排列组合
那么对应的背包问题就是下面我们要讲的背包分类
常见的背包类型主要有以下几种：
1、0/1背包问题：每个元素最多选取一次
2、完全背包问题：每个元素可以重复选择
3、组合背包问题：背包中的物品要考虑顺序
4、分组背包问题：不止一个背包，需要遍历每个背包
而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
1、最值问题：要求最大值/最小值
2、存在问题：是否存在…………，满足…………
3、组合问题：求所有满足……的排列组合
因此把背包类型和问题类型结合起来就会出现以下细分的题目类型：
1、0/1背包最值问题
2、0/1背包存在问题
3、0/1背包组合问题
4、完全背包最值问题
5、完全背包存在问题
6、完全背包组合问题
7、分组背包最值问题
8、分组背包存在问题
9、分组背包组合问题
这九类问题我认为几乎可以涵盖力扣上所有的背包问题
01背包
目标和：转化问题以后为0-1背包方案数问题。
分割等和子集：转化后为0-1背包可行性问题。
最后一块石头的重量 II：转化后为0-1背包最小值问题。
完全背包
零钱兑换：完全背包最小值
完全平方数：完全背包最小值
零钱兑换 II：完全背包方案数
组合总和 Ⅳ：考虑物品顺序的完全背包方案数。每个物品可以重复拿，有几种装满背包的方案？
多维背包
01 字符构成最多的字符串：多维费用的 0-1 背包最大值，两个背包大小：0和1的数量
盈利计划：多维费用的 0-1 背包最大值
分组背包
掷骰子的N种方法：每一组是一个骰子，每个骰子只能拿一个体积为1到6的物品
首先先了解一下原始背包问题的解题思路和代码：
最开始的背包问题是二维动态规划
// 0-1背包问题模板代码(二维)
void bags()
{
vector weight = {1, 3, 4}; //各个物品的重量
vector value = {15, 20, 30}; //对应的价值
int bagWeight = 4; //背包最大能放下多少重的物品
// 二维数组：状态定义:dp[i][j]表示从0-i个物品中选择不超过j重量的物品的最大价值
vector> dp(weight.size() + 1, vector(bagWeight + 1, 0));
// 初始化:第一列都是0，第一行表示只选取0号物品最大价值
for (int j = bagWeight; j >= weight[0]; j--)
dp[0][j] = dp[0][j - weight[0]] + value[0];
// weight数组的大小 就是物品个数
for (int i = 1; i < weight.size(); i++) // 遍历物品(第0个物品已经初始化)
{
for (int j = 0; j <= bagWeight; j++) // 遍历背包容量
{
if (j < weight[i]) //背包容量已经不足以拿第i个物品了
dp[i][j] = dp[i - 1][j]; //最大价值就是拿第i-1个物品的最大价值
//背包容量足够拿第i个物品,可拿可不拿：拿了最大价值是前i-1个物品扣除第i个物品的 重量的最大价值加上i个物品的价值
//不拿就是前i-1个物品的最大价值,两者进行比较取较大的
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout << dp[weight.size() - 1][bagWeight] << endl;
}
二维代码可以进行优化，去除选取物品的那一层，简化为一维背包
动态规划：关于01背包问题，你该了解这些！（滚动数组）
对于背包问题其实状态都是可以压缩的。
在使用二维数组的时候，
递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，
表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，
不如只用一个一维数组了，
只用dp[j]（一维数组，也可以理解是一个滚动数组）。
这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。
遍历背包的顺序是不一样的：
二维dp遍历的时候，背包容量是从小到大
而一维dp遍历的时候，背包是从大到小。
二维：
因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
一维：
如果正序遍历，那么物品0就会被重复加入多次！倒序遍历是为了保证物品i只被放入一次！
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
举例推导dp数组
一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：
void test_1_wei_bag_problem()
{
vector weight = {1, 3, 4};
vector value = {15, 20, 30};
int bagWeight = 4;
// 初始化
// 一维 dp 状态定义：dp[j]表示容量为j的背包能放下东西的最大价值
vector dp(bagWeight + 1, 0);
for (int i = 0; i < weight.size(); i++)
{ // 遍历物品
for (int j = bagWeight; j >= weight[i]; j--)
{ // 遍历背包容量(一定要逆序)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //不取或者取第i个
}
}
cout << dp[bagWeight] << endl;
}
1、两层循环
分别遍历物品nums和背包容量target
2、转移方程
根据背包的分类：确定物品和容量遍历的先后顺序
根据问题的分类：确定状态转移方程的写法
1、0/1背包：
外循环nums,
内循环target,
target倒序且target>=nums[i];
（01背包用的是上一轮的结果，所以要倒序）
//dp[j] 全部初始化为0
dp[j] = max（dp[j]，dp[j- weight[i]] + value[i]）
此时的dp[j]其实是跟 上一个i-1的时候的dp[j] 去比较 （上一个的dp[j]是不能取到第i件物品的）。
如果能取到第i个物品(第i件物品能不能放下)，那么就比较不取第i件物品(dp[j])跟取到第i件物品的价值(dp[j- weight[i]] + value[i])。更新之后的dp[j]取较大值
dp[j]是能取第i件以及之前所有物品的最大价值，每次的比较都是围绕能取第i件（含之前的物品）以及第i-1件（含之前的物品）的价值。
2、完全背包：
外循环nums,
内循环target,
target正序且target>=nums[i];
完全背包中相反，采用顺序。
举例，第i件物品重量是1，价值是value；
那么这个时候要先更新dp[1]，比较前i-1件物品的dp[1]以及value；
然后到dp[2]，dp[2]就应该max（前i件物品的dp[2-1]+value，前i-1件物品的dp[2-1]）然后跟前i-1件物品的f[2]比较。
dp[3]同理。一路推到dp[j]。
完全背包比较的应该是：前i件物品的f[v-weight]+value，前i-1件物品的f[v-weight]，前i-1件物品的f[v]这三者的比较。也就是当前状态，需要先推导出重量v之前的当前状态，才能得到最大值。
3、组合背包：
外循环target,
内循环nums,
target正序且target>=nums[i];
4、分组背包：
这个比较特殊，需要三重循环：
外循环背包bags,
内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板
看下标是从0开始 num=nums[j]
还是从1开始 num=nums[j-1]
1、最值问题:
dp[j] = max/min(dp[j], dp[j-num]+1) 或
dp[j] = max/min(dp[j], dp[j-num]+num);
2、存在问题(bool)：
dp[j]=dp[j] || dp[j-num];
3、组合问题：
dp[j]=dp[j]+dp[j-num];
1049. 最后一块石头的重量 II
思路：
最重要的是怎么转化为01背包问题
1、问题转化为：把一堆石头分成两堆,求两堆石头重量差最小值
进一步分析：
要让差值小,两堆石头的重量都要接近sum/2;
我们假设两堆分别为A,B,
A
若A更接近sum/2,B也相应更接近sum/2
2、进一步转化：将一堆stone放进最大容量为sum/2的背包,求放进去的石头的最大重量MaxWeight,
3、最终答案即为sum-2*MaxWeight;
二维dp
dp[i][j]:
从前i块石头中选取，选取值之和小于等于目标值j的最大值为dp[i][j]。（i、j分别对应从外到内两层循环。）
class Solution {
public:
int lastStoneWeightII2(vector &stones){
int n=stones.size();
int sum=accumulate(stones.begin(), stones.end(), 0);
int target=sum/2;
vector> dp(n+1,vector(target+1,0));
for (int i=1; i<=n; i++){
int cur=stones[i-1];
for (int j=1; j<=target; j++){
if(j=x
dp[i][j]=fmax(dp[i-1][j], dp[i-1][j-cur]+cur);
}
}
}
return sum-dp[n][target]-dp[n][target];
}
};
一维dp
dp[[j]:
表示容量为j的背包能放下东西的最大价值为dp[j]
class Solution {
public:
int lastStoneWeightII(vector &stones){
int n=stones.size();
int sum=accumulate(stones.begin(), stones.end(), 0);
int target=sum/2;
vector dp(target+1);
for (int i=1; i<=n; i++){
int cur=stones[i-1];
for (int j=target; j>=cur; j--){
if(j 416. 分割等和子集
二维dp：
dp[i][j]:
对nums的前i个元素进行选取，dp[i][j]记录是否存在选取值相加结果为目标值j。
（dp是bool型）（i、j分别对应从外到内两层循环。）
class Solution {
public:
bool canPartition2(vector& nums) {
int n=nums.size();
if(n<2) {
return false;
}
int sum = accumulate(nums.begin(), nums.end(), 0);
int maxNum = *max_element(nums.begin(), nums.end());
if(sum & 1) {
return false;
}
int target=sum /2;
if (maxNum>target) {
return false;
}
vector> dp(n+1, vector(target + 1, 0));
for (int i=0; i<=n; i++)
dp[i][0]=1;
for(int j=1; j<=target; j++)
dp[0][j]=0;
dp[0][0]=1;
for (int i=1; i<=n; i++) {
int num=nums[i-1];
for (int j=1; j<=target; j++){
if (j 一维dp：
dp[j]:
dp[j]记录是否存在选取值相加结果为目标值j。
class Solution {
public:
bool canPartition(vector &nums){
int n=nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) //如果是和为奇数显然无法分成两个等和子集
return false;
int target = sum / 2;
vector dp(target + 1, 0); //dp[i]:是否存在子集和为i
dp[0] = true; //初始化：target=0不需要选择任何元素，所以是可以实现的
for (int i=1; i<=n; i++){
int cur=nums[i-1];
for (int j=target; j>=cur; j--){
dp[j]=dp[j] || dp[j-cur];
}
}
return dp[target];
}
};
494. 目标和
思路：
热评
sum( P ) 转化为01背包问题
用价值和重量都为nums数组的物品，较好凑满x=(target + sum)/2的背包方案数
二维数组：
dp[i][j]：
为前 i 位置中选取，能凑满值为目标值 j 的方案数为dp[i][j]
class Solution {
public:
//dp
int findTargetSumWays(vector& nums, int target) {
int n=nums.size();
int sum=accumulate(nums.begin(), nums.end(), 0);
if(sum> dp(n+1,vector(target+1,0));
//边界
for(int i=0;i<=n;i++)
dp[i][0] = 0;
for(int j=1;j<=target;j++)
dp[0][j] = 0;
dp[0][0]=1;
for(int i=1;i<=n;i++){
int num=nums[i-1];//索引为i（从1开始）
for(int j=0;j<=target;j++){
if(j 一维数组：
1.状态定义:
dp[j]为恰好能凑满目标值为j的背包方案数
2.状态转移:
背包容量能或者不能装下nums[i]
（1）当不能装下nums[i]时, 方案数直接继承之前的dp[j]
dp[j]=dp[j];
（2）当能装下nums[i]时, 方案数= 不考虑nums[i]的方案数 + 有nums[i]参与新增的方案数
dp[j]=dp[j]+dp[j-num[i]];
3.状态初始化:
dp[0]=1,因为后面总会一直查找至j=0,如dp[3] += dp[3-3],空集是任意一条有效路径的起点,当属一条
4.遍历顺序:
i正序,j倒序
5.返回形式:
dp[target]就是凑成target的总的方案数
class Solution {
public:
int findTargetSumWays(vector& nums, int target) {
int n=nums.size();
int sum=accumulate(nums.begin(), nums.end(), 0);
if(sum dp(target+1,0);
//边界
dp[0]=1;
for(int i=1;i<=n;i++){
int num=nums[i-1];//索引为i（从1开始）
for(int j=target;j>=num;j--){
if(j 322. 零钱兑换
二维dp：
dp[i][j]:用前i个给定硬币能换到面值为j的最小硬币数量
class Solution {
public:
int coinChange(vector &coins, int amount){
//给dp数组每个位置赋初值为Max是为了最后判断是否能填满amount
int n=coins.size();
int Max=amount+1;
vector> dp(n+1,vector(amount+1, Max));
dp[0][0] = 0;
for (int i=1;i<=n;i++){
dp[i][0]=0;
}
for (int i=1;i<=n;i++){
int coin=coins[i-1];
for (int j=1; j<=amount; j++){
if(j>=coin)
dp[i][j] = fmin(dp[i-1][j], dp[i][j - coin] + 1);
else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[n][amount] == Max ? -1 : dp[n][amount];
}
};
一维dp：
dp[j]:换到面值j所用的最小硬币数量
class Solution {
public:
int coinChange(vector &coins, int amount){
//给dp数组每个位置赋初值为INT_MAX是为了最后判断是否能填满amount
//要用long long 类型
int n=coins.size();
vector dp(amount+1, INT_MAX);
//dp[i]:换到面值i所用的最小数量
dp[0] = 0;
for (int i=1;i<=n;i++){
int coin=coins[i-1];
for (int j = 1; j <= amount; j++){
if(j>=coin)
dp[j] = fmin(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
279. 完全平方数
二维dp：
dp[i][j]:用[1-i]个整数的平方数 能凑到 和为j 的最小整数个数
class Solution {
public:
int numSquares(int n){
vector> dp(sqrt(n)+1,vector(n+1, INT_MAX));
dp[0][0]=0;
for(int i=0;i<=sqrt(n);i++){
dp[i][0]=0;
}
for (int i=1; i<=sqrt(n); i++){
int num=i*i;
for (int j=1; j<=n; j++){
if(j>=num)
dp[i][j] = fmin(dp[i-1][j], dp[i][j - num] + 1);
else
dp[i][j]=dp[i-1][j];
}
}
return dp[sqrt(n)][n];
}
};
一维dp：
dp[j]:用[1-sqrt(n)]个整数的平方数 能凑到 和为j 的最小整数个数
class Solution {
public:
int numSquares(int n){
//dp[i]:和为i的完全平方数的最小数量
vector dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= sqrt(n); i++){
int num=i*i;
for (int j = 1; j <= n; j++){
if (j >= num)
dp[j] = min(dp[j], dp[j-num]+1);
}
}
return dp[n];
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）