动态规划背包问题

背包问题主要是背模板这里收录了一些模板一些复杂的背包问题如泛化物品未收录01背包问题无优化for(int i1;in;i) { for(int c0;cm;c) { f[i][c]f[i-1][c]; if(cw[i]) f[i][c]max(f[i][c],f[i-1][c-w[i]]v[i]); } }一维数组优化for(int i1;in;i) { for(int cm;c0;c--) { if(cw[i]) f[c]max(f[c],f[c-w[i]]v[i]); } }更进一步的常数优化for(int i1;in;i) { sumww[i]; boundmax(m-sumw,w[i]); for(int cm;cbound;c--) { if(cw[i]) f[c]max(f[c],f[c-w[i]]v[i]); } }完全背包问题for(int i1;in;i) { for(int c0;cm;c) { if(cw[i]) f[c]max(f[c],f[c-w[i]]v[i]); } }多重背包问题for(int i1;in;i) { if(w[i]*a[i]m) { for(int c0;cm;c) { if(cw[i]) f[c]max(f[c],f[c-w[i]]v[i]); } } else { k1;amounta[i]; while(kamount) { for(int ck*w[i];c0;c--) { if(cw[i]) f[c]max(f[c],f[c-w[i]]k*v[i]); } amount-k; k1; } for(int camount*w[i];c0;c--) { f[c]max(f[c],f[c-w[i]]amount*v[i]); } } }