三大背包问题---动态规划

三大背包问题分别是：

（背包问题是动态规划的经典问题，如果你连基本动态规划或者是DFS搜索的思维都没有的话，我不建议你看着一篇博客）

1.01背包

2.完全背包

3.自增背包

首先是 01背包

01背包表示的是有 n件物品，每一件物品有w的质量，同时每一件物品也有v的价值，求问在选取质量不超过 M 的情况下使得所选取的物品价值V最大，输出这个V

很明显，遇到这类题目，对于每一个问题，我们有选取和不选取两种解法，对应的我们可以建立一颗完全二叉树进行DFS搜索，使得选取物品放在左边，不选取物品放在右边，但是注意，这样的解法显然不是最优方法，只适用于在物品数量不大于20的情况（即n数量很小），才可以正常允许，通常情况，我们将要采取DP做法（动态规划01背包做法）

题库相应题目：https://www.dotcpp.com/oj/problem1100.html   ----采药

那么对应着，我们可以开辟二维数组，对于每一个状态拥有选取和不选区的两种状态，我们只需要两层循环式的去记忆其当时选取的最大值即可，参考

#include<iostream>
#include<cmath>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int Value_max=1005;
const int Time_max=105;
 
int dp[Time_max][Value_max]= {0}; //动态规划 
int value[Value_max]= {0};    //价值 
int cost[Time_max]= {0};  //耗时 
 
int total_time;    //总时间 
int n;         //总药品的数量 
 
void knapsack() { //01背包算法 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=total_time; j++) {
            if(cost[i]>j) {
                dp[i][j]=dp[i-1][j]; 
            } else {
                dp[i][j]=max(dp[i-1][j-cost[i]]+value[i],dp[i-1][j]);
            }
        }
    }
}
 
int main() {
    hh;
    cin>>total_time>>n;
    for(int i=1; i<=n; i++) {
        cin>>cost[i]>>value[i];
    }
    knapsack();
    cout<<dp[n][total_time]<<endl;
    return 0;
}

上述代码来自我自己的题解。这位大佬的题解更加的全面和详细：https://blog.dotcpp.com/wenyajie/3407

但是这样的做法仅仅只是满足本题目，通常情况的题目01背包还会提出各种限制和假设，再单独开辟二维数组有可能就造成空间情况吃紧了，因此我们可以采用滚动数组压位的方法，将二维的数组压缩到一维，以便再添加各类条件，也是对内存的妥善利用

采药这一题两种方法的代码可以参考我的题解：https://blog.dotcpp.com/Mustenaka/57806

#include<bits/stdc++.h>
using namespace std;
int dp[1005];//滚动数组的写法，省下空间省不去时间
int weight[1005];
int value[1005];
int main()
{
    int n,m;
    cin>>m>>n;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
        cin>>weight[i]>>value[i];
    for(int i=1; i<=n; i++)//对每个数判断，可反
    {
        for(int j=m; j>=weight[i]; j--)//这里这个循环定死，不能反,反了就是完全背包
        {
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);//其实不断在判断最优解，一层一层的
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

其次是 完全背包

完全背包和01背包的区别就是，01背包的每一件物品可以选取1次，而完全背包的每一件物品都是可以重复选取得（就是每一件物品可以选取无数次），完全背包的做法与压缩维度版本的01背包只相差了第二层循环的判断语句上面，其余几乎完全一样

题库题目：我还没有找到 百度有一大堆

相对于的代码可以从上文修改为：

memset(dp, 0, sizeof(dp));
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])
    }
}

最后是 自增背包（多重背包）

自增背包的主要区别就是，对于每一件物品，它只能选取K次，其余则与01背包的要求没有变化，那么对于自增背包，我们可以先进行一个简单的判断，看看是否全部选取K次之后能够满足最大值的条件，这样就是一个 完全背包 的数学模型，可以利用完全背包的思维快速写完，如果不行的话，他可以理解位k次的01背包，则将01背包进行扩展即可解决（注意这只是一个朴素思维的解法）

题库题目：我也还没有找到 百度上面有一大堆

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1000000
using namespace std;
int dp[MAX];//存储最后背包最大能存多少
int value[MAX],weight[MAX],number[MAX];//分别存的是物品的价值，每一个的重量以及数量
int bag;
void ZeroOnePack(int weight,int value ) { //01背包
    int i;
    for(i = bag; i>=weight; i--) {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
void CompletePack(int weight,int value) { //完全背包
    int i;
    for(i = weight; i<=bag; i++) {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
 
void MultiplePack(int weight,int value,int number) { //多重背包
    if(bag<=number*weight) { //如果总容量比这个物品的容量要小，那么这个物品可以直到取完，相当于完全背包
        CompletePack(weight,value);
        return ;
    } else { //否则就将多重背包转化为01背包
        int k = 1;
        while(k<=number) {
            ZeroOnePack(k*weight,k*value);
            number = number-k;
            k = 2*k;//这里采用二进制思想
        }
        ZeroOnePack(number*weight,number*value);
    }
}
int main() {
    int n;
    while(~scanf("%d%d",&bag,&n)) {
        int i,sum=0;
        for(i = 0; i<n; i++) {
            scanf("%d",&number[i]);//输入数量
            scanf("%d",&value[i]);//输入价值  此题没有物品的重量，可以理解为体积和价值相等
        }
        memset(dp,0,sizeof(dp));
        for(i = 0; i<n; i++) {
            MultiplePack(value[i],value[i],number[i]);//调用多重背包,注意穿参的时候分别是重量，价值和数量
        }
        cout<<dp[bag]<<endl;//容量为bag的最优解
    }
    return 0;}

以上为三大背包问题的基本模板和思维，希望对各位做题有一定帮助