总结：动态规划（3）完全背包&&面试背包问题总结

文章目录

完全背包

完全背包和01背包的区别就是物品是否可以重复选取

有N件物品和⼀个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。

物品都有无数个，问将哪些物品装入背包里，物品价值总和最大？

在01背包里面，如果使用滚动数组，对遍历顺序有要求，必须先遍历物品，再遍历背包，并且遍历背包需要从大到小，防止物品被重复添加；

在完全背包里面，对于遍历顺序没有要求，可以先遍历物品，也可以先遍历背包，但是，由于物品的数量不限，所以遍历背包的时候，我们要从小到大遍历，保证物品被重复添加；

#include<bits/stdc++.h>
using namespace std;
class Solution{
   
public:
int maxValue(int bagWeight,vector<int>& weight,vector<int>& value)
{
   
//dp[i][j]:用下标0到i的物品去填容量为j的背包，最大的价值为多少
vector<int> dp(bagWeight+1);
for(int i=0;i<weight.size();++i)//先遍历物品
{
   
//for(int j=bagWeight;j>=weight[i];--j)
for(int j=weight[i];j<=bagWeight;++j)//再从小到大遍历背包
{
   
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
for(int k=0;k<dp.size();++k)
cout<<dp[k]<<" ";
cout<<endl;
}
//先遍历背包，再遍历物品
/* for(int j=1;j<=bagWeight;++j) { for(int i=0;i<=weight.size();++i) { if(j>=weight[i]) dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); } }*/
return dp[bagWeight];
}
};

int main()
{
   
Solution A;
vector<int> weight = {
   1, 3, 4};
vector<int> value = {
   15, 20, 30};
int bagWeight = 4;
int ans=A.maxValue(bagWeight,weight,value);
return 0;
}

518 零钱兑换II

给定不同⾯额的硬币和⼀个总⾦额。写出函数来计算可以凑成总⾦额的硬币组合数。假设每⼀种⾯额的硬币有⽆限个。

完全背包，物品价值=重量
求组合数，所以递推dp[i][j]=dp[i-1][j]+dp[i-1][j-weight[i]] ;翻译翻译就是：用下标[0,i]的物品填容量为j的背包的组合方案=用下标[0,i-1]的物品填容量为j的背包的组合方案+用下标[0,i-1]的物品填容量为j-weight[i]的背包的组合方案（在此基础上再往里面放物品i）

class Solution {
   
public:
    int change(int amount, vector<int>& coins) {
   
        //完全背包，重量=价值
        vector<int> dp(amount+1,0);
        dp[0]=1;//初值，dp[1]+=dp[0],是计算其他dp的基础
        for(int i=0;i<coins.size();++i)
        {
   
            for(int j=coins[i];j<=amount;++j)
            {
   
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

377 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

这道题目与上面题目不同的是：顺序不同的组合算是两种组合，因此求的是排列数；

那么，就需要先遍历背包，再遍历物品；

class Solution {
   
public:
    int combinationSum4(vector<int>& nums, int target) {
   
        //实际上求的排列方案个数
        vector<int> dp(target+1,0);
        dp[0]=1;
        for(int j=1;j<=target;++j)
        {
   
            for(int i=0;i<nums.size();++i)
            {
   
                if(j>=nums[i]&&dp[j]<INT_MAX-dp[j-nums[i]])
                    dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};

总结

完全背包与01背包的不同是物品是否可以重复取；
纯完全背包，两层for循环没有特别要求，但是，当求组合数的时候，需要先遍历物品，再遍历背包，并且背包是从小到大遍历；求排列数的时候，先遍历背包，再遍历物品；

70 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数。

之前解决这道题目的时候，我们采用经验或者说斐波那契来做：dp[j]=dp[j-1]+dp[j-2] ，翻译翻译就是从j-1往上一次跳一阶+从j-2往上一次跳两阶；现在懂了完全背包后，发现，这个就是一个简化了的完全背包问题。背包容量为n，物品的重量等于价值，物品可以随意取。题目求的是不同的方法到达顶点，那么相当于求组合数，然后顺序不一样的组合属于两种组合，因此，最终需要求的是排列数；根据前面的经验：

完全背包两层for循环无顺序而言，只要求遍历背包从小到大，保证物品被重复添加
求排列数要求遍历背包在外循环，遍历物品在内循环

class Solution {
   
public:
    int climbStairs(int n) {
   
        //使用完全背包的问题，求排列数
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=n;++i)//先遍历背包
        {
   
            for(int j=1;j<=2;++j) //再遍历物品
            {
   
                if(i>=j) dp[i]+=dp[i-j];//求排列数
            }
        }
        return dp[n];
    }
};

322 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

完全背包，求填满背包的物品最小个数，不是组合也不是排列，因此两层for循环顺序无所谓
递推公式：dp[j]=min(dp[j],dp[j-weight[i]]+1)

class Solution {
   
public:
    int coinChange(vector<int>& coins, int amount) {
   
        //完全背包，求满足填满背包的最小硬币个数；
        //求组合数，因此两层for循环的顺序随意
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();++i)
        {
   
            for(int j=coins[i];j<=amount;++j)
            {
   
                if(dp[j-coins[i]]!=INT_MAX)
                    dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX? -1:dp[amount];
    }
};

279 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

一看题目就是完全背包，数字可以重复使用；
求装满背包的完全平方数的最小个数，那么就是两层for循环无所谓顺序；
递推公式：dp[j]=min(dp[j],dp[j-i*i]+1) ; 这个地方我疑惑过，后来发现和之前的求价值是一个意思，这个递推的二维形式是：dp[i][j]=min(dp[i-1][j],dp[i-1][j-i*i]+1) =min(用下标[0,i-1]的物品装满背包j,用下标[0,i]的物品装满背包j) ，然后，翻译翻译就是，min(用下标[0,1]的物品装满背包j,用下标[0,2]的物品装满背包j，用下标[0,3]的物品装满背包j，…，用下标[0,i]的物品装满背包j)

class Solution {
   
public:
    int numSquares(int n) {
   
        //完全背包问题：求满足背包容量的最小物品数，两层for循环无所谓顺序
        //dp[j]:和为j的完全平方数的最小数量
        vector<int> dp(n+1,100000);
        dp[0]=0;
        for(int i=1,a=i*i;a<=n;)
        {
   
            for(int j=a;j<=n;++j)
            {
   
                dp[j]=min(dp[j],dp[j-a]+1);
            }
            ++i;
            a=i*i;
        }
        return dp[n];
    }
};

139 单次拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

背包就是s的长度
物品是什么？就是s中的子串
dp[i]：s中从下标0出发长度为i的字符串是否可以被拆分为列表中单词的组合
递推公式：dp[i]=dp[j]&&s.substr(j,i-j)是否在字典中出现
set的初始化可以直接使用其他容器的迭代器，上一次用list初始化vector也是同样的道理
遍历顺序：为什么先遍历背包再遍历物品，可以调换吗？可以的，先遍历背包，是因为为了方便取子串
初始值：dp[0]=true 题目中说了非空单次列表和非空字符串

class Solution {
   
public:
    bool wordBreak(string s, vector<string>& wordDict) {
   
        // 完全背包 排列 
        //dp[j]表示
        unordered_set<string> mySet(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1;i<=s.size();++i)//遍历背包
        {
   
            for(int j=0;j<i;++j)//遍历物品
            {
   
                //如果dp[j]为true，且s中[j,i-j]的字符子串出现在wordDict中，那么dp[i]就为true
                string word=s.substr(j,i-j);
                if(mySet.find(word)!=mySet.end()&&dp[j])
                    dp[i]=true;
            }
        }
        return dp[s.size()];
    }
};

多重背包

多重背包就是背包的数量是有限个，翻译翻译就是，同样的东西有好几个，因此，可以通过将相同的物品当成两个物品来转换为一种01背包

有N种物品和⼀个容量为V的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci，价值是Wi 。求解将哪些物品装⼊背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最⼤。

假设背包容量为10，物品价格、数量、价值如下：

将重复的物品添加到物品序列里面，然后用01背包的方法去做
在01背包里面，循环物品的时候，对于相同的物品，加一层循环

#include<bits/stdc++.h>
class Solution{
   
public:
    int maxValue(int bagWeight,vector<int> weight,vector<int> value,vector<int> nums)
    {
   
        vector<int> dp(bagWeight+1,0);
        //问：01背包可以交换两层for循环吗？
        for(int i=0;i<weight.size();++i)//先遍历物品
        {
   
            for(int j=bagWeight;j>=weight[i];--j)//再遍历背包
            {
   
                for(int k=0;k<nums[i] && j>=(k+1)*weight[i];++k)//遍历相同的物品
                {
   
                    dp[j]=max(dp[j],dp[j-(k+1)*weight[i]]+(k+1)*value[i]);
                }
            }
        }
        return dp[bagWeight];
    }
};
int main()
{
   
    Solution A;
    vector<int> weight = {
   1, 3, 4};
    vector<int> value = {
   15, 20, 30};
    vector<int> nums = {
   2, 3, 2};
    int bagWeight = 10;
    int ans=A.maxValue(bagWeight,weight,value,nums);
    return 0;
}

总结

Carl哥总结的太到位了，经过几天的学习，感觉自己对动态规划背包问题的理解透彻了，现在回忆起暑期实习机试题目，有一道就是买糖果的问题，本质就是完全背包；

递推公式
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
装满背包有几种方法：dp[j]+=dp[j-nums[i]]
装满背包的最大价值：dp[j]=max(dp[j-weight[i]]+value[i],dp[j])
装满背包的物品最少个数：dp=min(dp[j],dp[j-weight[i]]+1)
遍历顺序
01背包
二维dp，遍历顺序无所谓，先遍历物品后遍历背包、先遍历背包后遍历物品都行，但第二维从小打大遍历（因为都是由左上角的元素推出右下角的元素）。初始化的时候从大到小赋值，防止重复添加
滚动数组，为了节省空间复杂度，此时，可以使用一维的数组来代替之前的二维dp，但是要求了遍历顺序和背包遍历的方向：必须先遍历物品，再遍历背包，并且背包从大到小遍历（为了使用滚动数组）
完全背包
纯完全背包 ：两层for循环无所谓
求组合数 ：先遍历物品，再遍历背包，背包从小到大遍历，保证物品重复添加
求排列数 ：先遍历背包，再遍历物品
求物品最小数 ：两层for循环无所谓顺序