01背包理论基础
01背包是有一个背包有M的容量 给我们N个物品每个物品有自己的价值 我们需要装进背包里尽可能获得最大的价值
分析题目 把背包想象成一个二维数组 先遍历每个物品放入背包里面 dp数组的含义表示的就是背包所含有的价值 当我们遍历物品1的时候我们要开始更新背包里面的物品 即对于物品1我们可以放可以不放 如果不放价值就是dp[i-1][j] 如果放的话 就是dp[i-1][j-weight[i]]+value[i] 所以我们最后的递推公式就是取两者的最大值 遍历顺序就是先遍历物品然后在遍历背包的容量
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,bag;
cin>>n>>bag;
vector<int> weight(n,0);
vector<int> value(n,0);
for(int i = 0; i < n; i++) {
cin >> weight[i];
}
for(int j = 0; j < n; j++) {
cin >> value[j];
}
vector<vector<int>> dp(weight.size(),vector<int>(bag+1,0));
for (int j = weight[0]; j <= bag; j++) {
dp[0][j] = value[0];
}
for(int i=1;i<weight.size();i++){
for(int j=0;j<=bag;j++){
if(j<weight[i]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);
}
}
}
cout<<dp[n-1][bag]<<endl;
return 0;
}这道题还有第二个滚动数组的方法 就是用一个数组来表示 遍历物品0的时候就放入背包 然后再遍历背包但是需要我们从容量最大往小遍历（倒序遍历是为了保证每一个物品只会被加进去一次）
// 外层循环遍历每个类型的研究材料
for (int i = 0; i < M; ++i) {
// 内层循环从 N 空间逐渐减少到当前研究材料所占空间
for (int j = N; j >= costs[i]; --j) {
// 考虑当前研究材料选择和不选择的情况，选择最大值
dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
}
}416 分割等和子集
我们可以把这一题抽象成一个背包问题 题目要求分割两个子集且元素和相等 我们可以先计算出该数组的总和 然后对半分 即代表了背包的容量 然后我们要用物品刚好填满这个背包 如果可以填满（dp数组的值等于下标 因为数字即代表重量也代表价值） 则说明可以分割
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;
vector<int> dp(10001,0);
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
if(sum%2==1) return false;
int target = sum/2;
for(int i=0;i<nums.size();i++){
for(int j=target;j>=nums[i];j--){
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
if(dp[target]==target) return true;
else return false;
}
};1049 最后一块石头的重量II
两块石头相撞等价于两组石头相撞 所以我们只要求出来两组石头相撞最小重量 就代表两组重量相近就是最小的即我们要越接近总重量的一半 这样就可以抽象成一个背包问题
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) sum += stones[i];
int target = sum / 2;
for (int i = 0; i < stones.size(); i++) {
for (int j = target; j >= stones[i]; j--) {
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};474.一和零
该题目就相当于我们要同时满足两个维度的背包一个是0一个是1 所以我们需要用到二维数组 每一个字符串的元素都可以放或者不放 如果放进去就是dp[i-zero][j-one]+1
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(string str:strs){
int one=0,zero=0;
for(char c:str){
if(c=='0') zero++;
else one++;
}
for(int i=m;i>=zero;i--){
for(int j=n;j>=one;j--){
dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1);
}
}
}
return dp[m][n];
}
};完全背包理论基础
它和01背包的不同点 就是每一个物品你可以放无限次 我们知道用滚动数组的方法做01背包 遍历背包容量的时候要从大到小遍历是为了防止物品被放入多次 所以完全背包我们就可以从小到大遍历（从当前物品的重量开始遍历）
// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << endl;
}518.零钱兑换II
求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
本题问我们有多少种方法 我们可以把dp数组初始化成1 dp数组表示有多少个方案可以用所给硬币凑成金额为下标这么多的数 然后amount就是背包容量 coins就是重量和价值 先遍历物品去放背包 然后再用第二个物品 每一次可以放进去的话 就加上之前的方案数
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0]=1;
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. 组合总和 Ⅳ
这道题目和组合不一样 它说明序列不同也是不一样的 说明这是一个排列的题目 求排列的话 我们就要先遍历背包 再去遍历物品 因为这样我们可以在同一个背包容量下 可以放进不同的物品就可以出现不同序列的情况
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,.0);
dp[0]=1;
for(int j=0;j<=target;j++){
for(int i=0;i<nums.size();i++){
if(j-nums[i]>=0 && dp[j]<INT_MAX - dp[j-nums[i]]){
dp[j]+=dp[j-nums[i]];
}
}
}
return dp[target];
}
};322. 零钱兑换
本题要求能凑成金额的最小硬币数 因为我们求最小 所以我们要把数组初始化成INT_MAX
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
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);
}
}
}
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};279.完全平方数
抽象成完全背包问题 凑成的数n就是背包的容量 然后每一个完全平方数就是我们的物品 我们要求最小的数量 就和上一道题的思路是一致的
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[0]=0;
for(int i=1;i*i<=n;i++){
for(int j=i*i;j<=n;j++){
dp[j]=min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
};139.单词拆分
该题目字符串s就是我们的背包 我们要用字典里面的单词去填满背包 这一题我们要求是排列数 因为单词的顺序会影响我们的判断 所以我们要先遍历背包 再遍历物品 我们找到一个单词就要标记一个true
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordset(wordDict.begin(),wordDict.end());
vector<bool> dp(s.size()+1,false);
dp[0]=true;
for(int j=1;j<=s.size();j++){
for(int i=0;i<j;i++){
string word = s.substr(i,j-i);
if(wordset.find(word)!=wordset.end() && dp[i]){
dp[j]=true;
}
}
}
return dp[s.size()];
}
};背包问题总结
