背包问题–01背包 （Bitset的优化） 多重背包 （二进制优化）ccsudeer-

01背包问题：

题目链接

题意：n个物品一个m容量的背包，n个物品有need[i]的体积消耗，以及权值value[i] ，问m容量装n个物品能得到的最大权值是多少。

做法：01背包介绍：博客

代码：

 #include<bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=5e2+10,M=1e5+10; int n,m,dp[M],need[N],value[N]; int main() {     n=read(),m=read();     for(int i=1;i<=n;++i){         need[i]=read(),value[i]=read();     }      for(int i=1;i<=n;++i){         for(int j=m;j>=need[i];--j){             dp[j]=max(dp[j],dp[j-need[i]]+value[i]);         }     }     printf("%dn",dp[m]); } 

Bitset优化01背包

需要更正一个地方是，这里的bitset优化的不是朴素的01背包，而是只有01状态的多重背包。

之前的博客：[博客C回到过去]  [题目链接 C回到过去]

 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100010; bitset<N>f[451],g[451];   int a[N],cnt[N],ans[N],anss; int main() {      int n,m;     scanf("%d%d",&n,&m);     for(int i = 1;i <= n;++i) scanf("%d",&a[i]);      sort(a + 1,a + n + 1);       int tot = 0;     for(int i = 1;i <= n;++i) {         if(a[i] != a[i - 1])  a[++tot] = a[i];         cnt[tot]++;     }      n = tot;      f[0][0] = 1;     g[n + 1][0] = 1;      for(int i = 1;i <= n;++i) {         int k = a[i],tmp = cnt[i];//f[i]|=f[i]<<a[i]代表f[i]取一个a[i]时的状态转移          f[i] = f[i - 1];          for(int j = 1;j <= tmp;tmp -= j,j <<= 1,k <<= 1) f[i] |= f[i] << k;         // 运用倍增(二进制)的思想，节约时间 并且能够覆盖所有的状态         //比如现在有5个1         //j=1 1一个1  可以 得到 bitset状态：000011（从后往前数从低位到高位，低位从0开始）         //j=2 那么倍增一下，两个1 ：之前的状态00011移两位得  001100         //或上之前得000011  得    001111   是不是得到0，1，2，3，都是1的情况         //需要注意的是现在我们应该是消耗了三个1了 j目前还是2。那么tmp就不是一成不变的，所以tmp-=j         //接着j继续乘2  j =4  由于5个1消耗了3  剩余两个，小于j   跳出for循环          //因为有剩余的部分，就继续组合一下         f[i] |= f[i] << (a[i] * tmp);     }      for(int i = n;i >= 1;--i) {         int k = a[i],tmp = cnt[i];          g[i] = g[i + 1];          for(int j = 1;j <= tmp;tmp -= j,j <<= 1,k <<= 1) g[i] |= g[i] << k;          g[i] |= g[i] << (a[i] * tmp);     }      for(int i = 1;i <= n;++i) {         int flag = 0;         for(int j = 0;j <= m;++j) {             if(f[i - 1][j] & g[i + 1][m - j]) {                 flag = 1;break;             }         }         if(!flag) ans[++anss] = a[i];     }  //  for(int i = 1;i <= n;++i) printf("%d %dn",a[i],cnt[i]);      printf("%dn",anss);     for(int i = 1;i <= anss;++i) printf("%d ",ans[i]);     return 0; } 

多重背包

来一道例题：题目链接

题意：n经费，m种类的大米，每种大米有 金额p[i] 重量h[i] 以及最多的袋数c[i]   问在n经费内 时能得到的最大重量是多少？

做法：朴素的多重背包

 #include<bits/stdc++.h> using namespace std;  typedef long long ll; const int N=1e2+10; int n,m,p[N],h[N],c[N],dp[N]; inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; }  int main() {     int _=read();while(_--)     {         n=read(),m=read();         for(int i=1;i<=m;++i) p[i]=read(),h[i]=read(),c[i]=read();          for(int i=0;i<=n;++i) dp[i]=0;          for(int i=1;i<=m;++i){//枚举种类             for(int j=1;j<=c[i];++j){//c[i]次的01背包                 for(int k=n;k>=p[i];--k){                     dp[k]=max(dp[k],dp[k-p[i]]+h[i]);                 }             }         }         printf("%dn",dp[n]);     } } 

二进制优化多重背包

题目链接：牛客E题

这部分做法参考来自：wiki

 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define IO ios::sync_with_stdio(false) #define pb push_back #define mk make_pair const int N = 1e5+10; const int mod = 1e9+7;  int n; int t[N], q[N], s[N]; int dp[2000];  int main(){     int h1, m1, h2, m2;     scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);     if(m1 > m2){         m2 += 60; h2--;     }     int sumt = (h2-h1)*60 + m2 - m1;     for(int i = 0; i <= sumt; i++){         dp[i] = 0;     }     for(int i = 1; i <= n; i++){         scanf("%d%d%d", t+i, q+i, s+i);     }     int index = 0;     for(int i = 1; i <= n; i++){         int c = 1;         if(s[i] == 0 || s[i] >= sumt/t[i]) {             for(int j = t[i]; j <= sumt; j++){//普通的完全背包                 dp[j] = max(dp[j], dp[j-t[i]] + q[i]);             }         }         else{             while(s[i] - c > 0){//多重背包的二进制优化                  s[i] -= c;                 for(int j = sumt; j >= c*t[i]; j--){                     dp[j] = max(dp[j], dp[j-c*t[i]] + c*q[i]);                 }                 c *= 2;             }             if(s[i]){                 for(int j = sumt; j >= s[i]*t[i]; j--){                     dp[j] = max(dp[j], dp[j-s[i]*t[i]] + s[i]*q[i]);                 }             }         }     }     printf("%dn", dp[sumt]);     return 0; }