01背包

n个物品，v的体积，求最多能装下的价值

每个物品只能拿一次

https://www.acwing.com/problem/content/2/

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,V,dp[1005] = {0};
    scanf("%d%d",&N,&V);
    for(int i=1,x,y;i<=N;i++){
        scanf("%d%d",&x,&y);
        for(int j=V;j>=x;j--){
            dp[j] = max(dp[j],dp[j-x]+y);
        }
    }
    printf("%d\n",dp[V]);
    return 0;
}

完全背包

n个物品，v的体积，求最多能装下的价值

每个物品可以拿无限次

https://www.acwing.com/problem/content/3/

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,V,dp[1005] = {0};
    scanf("%d%d",&N,&V);
    for(int i=1,x,y;i<=N;i++){
        scanf("%d%d",&x,&y);
        for(int j=x;j<=V;j++){
            dp[j] = max(dp[j],dp[j-x]+y);
        }
    }
    printf("%d\n",dp[V]);
    return 0;
}

 

多重背包

n个物品，v的体积，求最多能装下的价值

每个物品可以拿k_i次

https://www.acwing.com/problem/content/5/

一个优化：（二进制优化）

显然我们没有必要跑全k_i次，判断下能用完全背包的就用完全背包好了

不能用完全背包的，考虑一个等价的次数，即，每次取1个，2个，4个。。。k_i-2^j+1个

j是最大的能使k_i-2^j+1>0的数

也就是说我们将k_i二进制拆分了

时间复杂度为O(n*m*log(∑k_i))

另一个优化：（单调队列优化）

————咕咕咕——————

时间复杂度O(n*m)

https://www.acwing.com/problem/content/6/

/*author:revolIA*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
int main(){
    ll N,V,dp[20005] = {0};
    scanf("%lld%lld",&N,&V);
    for(ll i=1,x,y,z;i<=N;i++){
        scanf("%lld%d%lld",&x,&y,&z);
        if(x*z>V){
            for(int j=x;j<=V;j++){
                dp[j] = max(dp[j],dp[j-x]+y);
            }
        }else{
            for(ll tmp = 1;z-tmp+1 > 0;tmp <<= 1){
                ll k = (z-(tmp<<1)+1)<0?z-tmp+1:tmp;
                for(ll j=V;j>=x*k;j--){
                    dp[j] = max(dp[j],dp[j-x*k]+y*k);
                }
            }
        }
    }
    printf("%lld\n",dp[V]);
    return 0;
}

 

混合背包

前三个混在一起，加个if判断即可

https://www.acwing.com/problem/content/submission/7/

/*author:revolIA*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 2e4+7;
int dp[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--){
        int k,value,cnt;
        scanf("%d%d%d",&k,&value,&cnt);
        if(cnt == -1){
            for(int i=m;i>=k;i--){
                dp[i] = max(dp[i],dp[i-k]+value);
            }
        }else if(cnt == 0 || k*cnt>=m){
            for(int i=k;i<=m;i++){
                dp[i] = max(dp[i],dp[i-k]+value);
            }
        }else{
            for(int i=1;cnt-i+1>0;i<<=1){
                int tmp = (cnt-(i<<1)+1)<0?cnt-i+1:i;
                for(int j=m;j>=tmp*k;j--){
                    dp[j] = max(dp[j],dp[j-tmp*k]+tmp*value);
                }
            }
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

 

二维费用的背包问题

物体不止有体积这个限制条件，还有质量这个限制条件

n个物体，v的背包容积，m的负重限制，还是01背包只能拿一个

https://www.acwing.com/problem/content/submission/8/

/*author:revolIA*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int maxn = 1e3+7;
int dp[maxn][maxn];
int main(){
    int n,v,m;
    scanf("%d%d%d",&n,&v,&m);
    while(n--){
        int volum,weight,value;
        scanf("%d%d%d",&volum,&weight,&value);
        for(int i=v;i>=volum;i--){