這道題目是一個多重背包的題目，多重背包實際上就是把整個物品的件數(shù)拆分成a0?20+a1?21+a2?22+...an?2n且a=0或1這樣每一次最優(yōu)解實際上就是在之前的基礎(chǔ)上進(jìn)行的最優(yōu)解的累加，但是發(fā)現(xiàn)如果物品數(shù)量不是恰好是某幾個數(shù)之和，那么就會出現(xiàn)有幾個統(tǒng)計不到的情況，那么只要提出來單獨處理這多出來的件數(shù)的背包就好了。還有一點需要注意的就是背包的時候要倒著枚舉因為是1維數(shù)組，那么如果修改了當(dāng)前的值那么當(dāng)前的值就會被覆蓋，那么更新這個背包的時候就可能用到當(dāng)前這個背包的值，所以顯然不能這么干。
核心代碼：

while(k <= num){end = k*c;for(int V=m;V>=end;V--)f[V] = max(f[V], f[V-k*c]+wei*k);num -= k;k *= 2;}if(num > 0){end = num*c;for(int V=m;V>=end;V--)f[V] = max(f[V], f[V-num*c]+wei*num);}

這道題太裸了，主要是練習(xí)一下。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1000; const int MAXM = 1000; int n, m; int wei, c, num, f[MAXM+10]; int main(){int C;scanf("%d", &C);while(C--){memset(f, 0, sizeof f);scanf("%d%d", &m, &n);for(int i=1;i<=n;i++){scanf("%d %d %d", &c, &wei, &num);int k=1, end;if(num*c > m)num = m / c;while(k <= num){end = k*c;for(int V=m;V>=end;V--)f[V] = max(f[V], f[V-k*c]+wei*k);num -= k;k *= 2;}if(num > 0){end = num*c;for(int V=m;V>=end;V--)f[V] = max(f[V], f[V-num*c]+wei*num);}}printf("%d\n", f[m]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/JeremyGJY/p/5921711.html

總結(jié)

以上是生活随笔為你收集整理的【动态规划】【多重背包】[HDU 1291]悼念512汶川大地震遇难同胞――珍惜现在，感恩生活...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。