多重背包2进制优化

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int maxn=100; int main() { int f[maxn][maxn],tj[maxn],jz[maxn]; memset(f,0,sizeof(f)); memset(tj,0,sizeof(tj)); memset(jz,0,sizeof(jz)); int n,m,n1=0; while(cin >> n >> m && n && m) { for(int i=1;i<=n;i++) { int x,y,s,t=1; cin >> x >> y >> s; while(s>=t) { tj[++n1]=x*t; jz[n1]=y*t; s-=t; t*=2; } tj[++n1]=x*s; jz[n1]=y*s; } for(int i=1;i<=n1;i++) for(int j=m;j>=0;j--) if(j>=tj[i]) f[i][j]=max(f[i-1][j],f[i-1][j-tj[i]]+jz[i]); else f[i][j]=f[i-1][j]; cout << f[n1][m] << endl; } return 0; }