01背包

01背包

时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int f[N],v[N],c[N],n,m;

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      cin>>c[i]>>v[i];
    for(int i=1;i<=n;i++)
      for(int j=m;j>=c[i];j--)  //注意此处倒序
        f[j]=max(f[j],f[j-c[i]]+v[i]);
    cout<<f[m];
    return 0;
}

完全背包

完全背包
完全背包与01背包几乎一致，只是循环时是正序遍历的。
时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int f[N],v[N],c[N],n,m;

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      cin>>c[i]>>v[i];
    for(int i=1;i<=n;i++)
      for(int j=c[i];j<=m;j++)  //注意此处正序
        f[j]=max(f[j],f[j-c[i]]+v[i]);
    cout<<f[m];
    return 0;
}

正序的原因也很好理解，根据01背包那张图就可以知道

多重背包

直接拆分法

多重背包 I
我们把一个物品最多选m次转化为m个这样的物品，每个最多选1次，也就是01背包了。
时间复杂度$O(nm\sum_{i=1}^n s[i])$

#include <iostream>
#include <cstdio>

using namespace std;
const int N=1e4+5;
int f[N],n,m;
int v[N],w[N],s[N];

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
      for(int j=1;j<=s[i];j++)  //有s种这样的物品
        for(int k=m;k>=v[i];k--)    //01背包
          f[k]=max(f[k],f[k-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}

二进制拆分法

多重背包 II

#include <iostream>
#include <cstdio>

using namespace std;
const int N=2e4+5;
int f[N],n,V,m;
int v1[N],w1[N],s[N];
int v[N],w[N];

int main() {
    cin>>n>>V;
    for(int i=1;i<=n;i++)
      cin>>v1[i]>>w1[i]>>s[i];
    for(int i=1;i<=n;i++) {
        int r=1;
        while(s[i]>r) { //拆分
            s[i]-=r;
            v[++m]=r*v1[i]; //注意要乘上这一次拆分的个数
            w[m]=r*w1[i];
            r<<=1; 
        }
        if(s[i]>0) {    //最后有一个剩余
            v[++m]=s[i]*v1[i];
            w[m]=s[i]*w1[i];
        }
    }
    for(int i=1;i<=m;i++)   //普通01背包
      for(int j=V;j>=v[i];j--) 
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[V];
    return 0;
}

二维费用背包

二维费用背包
费用两维，那么状态也两维，不难写出代码

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int n,m,p;
int c[N],s[N],v[N],f[N][N];

int main () {
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
      cin>>c[i]>>s[i]>>v[i];
    for(int i=1;i<=n;i++)
      for(int j=m;j>=c[i];j--)
        for(int k=p;k>=s[i];k--)    //两维的转移，类似01背包
          f[j][k]=max(f[j][k],f[j-c[i]][k-s[i]]+v[i]);
    cout<<f[m][p];
    return 0;
}