1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; struct coinType{ int w; int v; coinType(int iv,int iw){ v = iv; w = iw; } }; vector<coinType> coin; int dp[2][105]; int main(){ int caseCnt; cin >> caseCnt; while (caseCnt--) { int m = 0,n = 0; cin >> m >> n; coin.clear(); int maxm = 0; for (int i = 0; i < n; i++) { int iv = 0,iw = 0,num = 0; cin >> iw >> iv >> num; maxm += iw*num; int factor = 1; while (num) { if (num >= factor) { num -= factor; coin.push_back(coinType(iv*factor,iw*factor)); factor *= 2; }else{ coin.push_back(coinType(iv*num,iw*num)); num = 0; } } } memset(dp, 0, sizeof(dp)); for(int i = 1;i <= coin.size();i++){ for (int j = 0; j <= m; j++) { if(j-coin[i-1].w >= 0) dp[i%2][j] = max(dp[(i-1)%2][j-coin[i-1].w]+coin[i-1].v,dp[(i-1)%2][j]); else dp[i%2][j] = dp[(i-1)%2][j]; } } cout << dp[coin.size()%2][m] << endl; } return 0; } |
这个是一个多重背包问题,其实多重背包就是01背包,举个例子(其实是扒的):
¤像如果某件物品的重量为1,价值为2,数量为1000
¤我们就可以拆分成:
¤重量为1,价值为2的物品 重量为2,价值为4的物品
¤重量为4,价值为8的物品 …
¤重量为256,价值为512的物品
¤重量为489,价值为489*2的物品
简要地说,就是先拿二进制拆,拆出来1,2,4,8,16,32。。。这样的,等到拆不动了(剩下的不够下一个2进制整幂了),就把剩下的单独拿出来当成一个新物品,这样就不会丢解了。拆分完之后不就变成01背包了嘛。