首页 > 代码库 > ZOJ 3164 Cookie Choice 分组背包 混合背包
ZOJ 3164 Cookie Choice 分组背包 混合背包
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3181
题意：
就是混合背包加分组背包，有的物品是01背包，有的是多重背包，有的是完全背包，同时物品还有不超过8组的分组，如果在同一组则最多只能选一种。问能不能恰好地用掉D的容量，并且使所获价值最大。
分析：
开始的想法是多开一个下标，先把没有分组的做了，在0的下标，然后分组分别在组号的下标里按顺序处理，是什么背包就用什么做法，不过一直WA，对拍小数据大数据都没啥问题（可能随机数据太弱），现在脑子有点晕也不想看了。。
然后就百度了= =。。照着别人的程序重写了一遍（其实就是抄了一遍。。），做法是，处于某个分组的背包先在tmp数组里做，然后tmp[容量]转移到w[所在分组][容量]，也就是得到了每个分组使用多少容量所能得到的最大价值，最后再一起转移给dp[]数组。然后就A了。。
然后顺带总结一下多重背包，最朴素的是单个拆成01背包，然后log级别的是用二进制来拆，即拆成1, 2, 4, ... 2^k, total - 2^(k+1) + 1的物品，每个的价值和体积都乘以前面的倍数，同样是01背包来做。
然后做这题主要是想练练多重背包的单调队列优化。
dp[i][j]表示到第i个物品用了j的容量的最大价值，dp[i][j] = max(dp[i-1][j-kv] + kw)，第i个物品的体积是v，那么对于固定的j，只能是从j-v，j-2v，j-kv转移过来的，他们的共同点就是关于v同余t(t=j%v)，我们改写转移方程为：
dp[i][t+jv] = max(dp[i-1][t+j‘v] + (j-j‘)w) = max(dp[i-1][t+j‘v]-j‘w) + jw (j-j‘<=物品i数量amount[i])，右侧的前一项最大值就可以用单调队列维护了，同时多一层循环，循环关于v的同余类(0 to v-1)
下面贴三个程序，第一个是wa的(说不定贴出来有人可以帮我找错呢)。。第二个多重背包拆二进制ac的（差不多是抄的。。罪过），第三个多重背包用单调队列优化（实际上只快了10msTAT）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 7 struct que{ 8 int v, p; 9 } q[1500]; 10 int n, d, G, oo, head, tail; 11 int k[1500], e[1500], p[1500]; 12 int dp[1500][10]; 13 bool ingroup[1500]; 14 char str[100000]; 15 vector<int> g[10]; 16 int in(int &pos) 17 { 18 int ans = 0, len = strlen(str); 19 while(pos < len && !(‘0‘ <= str[pos] && str[pos] <= ‘9‘)) pos ++; 20 if (pos == len) return 0; 21 while(pos < len && (‘0‘ <= str[pos] && str[pos] <= ‘9‘)){ 22 ans = ans * 10 + str[pos] - ‘0‘; 23 pos ++; 24 } 25 return ans; 26 } 27 int main() 28 { 29 while(scanf("%d%d", &n, &d) != EOF) 30 { 31 for (int i = 1; i <= n; i ++) 32 scanf("%d%d%d", k+i, e+i, p+i); 33 scanf("%d", &G); 34 memset(ingroup, false, sizeof(ingroup)); 35 if (G) getchar(); 36 for (int i = 1; i <= G; i++){ 37 g[i].clear(); 38 gets(str); 39 int pos = 0; 40 int id = in(pos); 41 while (id != 0){ 42 ingroup[id] = true; 43 g[i].push_back(id); 44 id = in(pos); 45 } 46 } 47 memset(dp, 128, sizeof(dp)); 48 oo = -dp[0][0]; 49 dp[0][0] = 0; 50 for (int i = 1; i <= n; i++){ 51 if (ingroup[i]) continue; 52 if (k[i] == 0 || p[i] * k[i] > d){ 53 for (int j = p[i]; j <= d; j++) 54 if (dp[j-p[i]][0] != -oo) 55 dp[j][0] = max(dp[j-p[i]][0] + e[i], dp[j][0]); 56 } 57 else if (k[i] == 1){ 58 for (int j = d; j >= p[i]; j--) 59 if (dp[j-p[i]][0] != -oo) 60 dp[j][0] = max(dp[j-p[i]][0] + e[i], dp[j][0]); 61 } 62 else{ 63 int maxl = p[i] * k[i]; 64 for (int j = 0; j < p[i]; j++){ 65 head = tail = 0; 66 for (int k = j, cnt = 0; k <= d; k += p[i], cnt++){ 67 while(head != tail && k - q[head].p > maxl) head++; 68 if (dp[k][0] != -oo){ 69 int tmp = dp[k][0] - cnt * e[i]; 70 while(head != tail && q[tail-1].v < tmp) tail --; 71 q[tail].p = k; q[tail++].v = tmp; 72 } 73 if (head != tail) 74 dp[k][0] = max(q[head].v + cnt * e[i], dp[k][0]); 75 } 76 } 77 } 78 } 79 for (int gi = 1; gi <= G; gi++){ 80 for (int t = 0; t < g[gi].size(); t++){ 81 int i = g[gi][t]; 82 if (k[i] == 1){ 83 for (int j = d; j >= p[i]; j--) 84 if (dp[j-p[i]][gi-1] != -oo) 85 dp[j][gi] = max(dp[j-p[i]][gi-1] + e[i], dp[j][gi]); 86 } 87 else{ 88 int maxl = p[i] * k[i]; 89 if (k[i] == 0) maxl = 2 * d; 90 for (int j = 0; j < p[i]; j++){ 91 head = tail = 0; 92 for (int k = j, cnt = 0; k <= d; k += p[i], cnt++){ 93 while(head != tail && k - q[head].p > maxl) head++; 94 if (dp[k][gi-1] != -oo){ 95 int tmp = dp[k][gi-1] - cnt * e[i]; 96 while(head != tail && q[tail-1].v < tmp) tail --; 97 q[tail].p = k; q[tail++].v = tmp; 98 } 99 if (head != tail)100 dp[k][gi] = max(q[head].v + cnt * e[i], dp[k][gi]);101 }102 }103 }104 }105 }106 int ans = -oo;107 for (int i = 0; i <= G; i++)108 if (dp[d][i] > ans) ans = dp[d][i];109 if (ans >= 0) printf("%d\n", ans);110 else printf("i‘m sorry...\n");111 }112 return 0;113 }
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn = 1500; 7 int N, D, G, oo; 8 int flag[maxn], k[maxn], e[maxn], p[maxn], tmp[maxn], dp[maxn]; 9 int w[10][maxn];10 char str[100000];11 void complete(int w, int v, int dp[])12 {13 for (int i = w; i <= D; i++)14 if (dp[i-w] != -oo)15 dp[i] = max(dp[i], dp[i-w] + v);16 }17 void zero_one(int w, int v, int dp[])18 {19 for (int i = D; i >= w; i--)20 if (dp[i-w] != -oo)21 dp[i] = max(dp[i], dp[i-w] + v);22 }23 int main()24 {25 while(scanf("%d %d", &N, &D) != EOF)26 {27 for (int i = 1; i <= N; i++)28 scanf("%d %d %d", k+i, e+i, p+i);29 scanf("%d", &G); getchar();30 memset(flag, 0, sizeof(flag));31 for (int i = 1; i <= G; i++){32 gets(str);33 int len = strlen(str);34 for (int j = 0; j < len;){35 if (str[j] >= ‘1‘ && str[j] <= ‘9‘){36 int sum = 0;37 while (str[j] >= ‘0‘ && str[j] <= ‘9‘){38 sum = sum * 10 + str[j] - ‘0‘;39 j++;40 }41 flag[sum] = i;42 }43 else j++;44 }45 }46 memset(dp, 128, sizeof(dp));47 oo = -dp[0];48 dp[0] = 0;49 for (int i = 1; i <= G; i++){50 memset(w[i], 128, sizeof(w[i]));51 w[i][0] = 0;52 }53 for (int i = 1; i <= N; i++){54 if (flag[i]){55 memset(tmp, 128, sizeof(tmp));56 tmp[0] = 0;57 }58 if (k[i] == 0 || k[i] * p[i] >= D)59 complete(p[i], e[i], flag[i] ? tmp : dp);60 else {61 int t = 1, cnt = k[i];62 while(t < cnt){63 zero_one(t * p[i], t * e[i], flag[i] ? tmp : dp);64 cnt -= t;65 t <<= 1;66 }67 zero_one(cnt * p[i], cnt * e[i], flag[i] ? tmp : dp);68 }69 if (flag[i]) for (int j = 0; j <= D; j++) w[flag[i]][j] = max(w[flag[i]][j], tmp[j]);70 }71 for (int i = 1; i <= G; i++)72 for (int v = D; v >= 0; v--)73 for (int j = 0; j <= v; j++)74 if (dp[v-j] != -oo && w[i][j] != -oo){75 dp[v] = max(dp[v], dp[v-j] + w[i][j]);76 }77 if (dp[D] >= 0) printf("%d\n", dp[D]);78 else printf("i‘m sorry...\n");79 }80 return 0;81 }
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn = 1500; 7 struct queue{ 8 int v, p; 9 } q[100000];10 int N, D, G, oo, head, tail;11 int flag[maxn], k[maxn], e[maxn], p[maxn], tmp[maxn], dp[maxn];12 int w[10][maxn];13 char str[100000];14 void complete(int w, int v, int dp[])15 {16 for (int i = w; i <= D; i++)17 if (dp[i-w] != -oo)18 dp[i] = max(dp[i], dp[i-w] + v);19 }20 void zero_one(int w, int v, int dp[])21 {22 for (int i = D; i >= w; i--)23 if (dp[i-w] != -oo)24 dp[i] = max(dp[i], dp[i-w] + v);25 }26 void multi(int w, int v, int t, int dp[]){27 int maxl = t * w;28 for (int j = 0; j < w; j++){29 head = tail = 0; 30 for (int k = j, cnt = 0; k <= D; k += w, cnt++){ 31 while(head != tail && k - q[head].p> maxl) head ++;32 if (dp[k] != -oo){33 int tmp = dp[k] - cnt * v;34 while(head != tail && q[tail-1].v < tmp) tail --;35 q[tail].p = k; q[tail++].v = tmp;36 }37 if (head != tail)38 dp[k] = max(dp[k], q[head].v + cnt * v);39 }40 }41 }42 int main()43 {44 while(scanf("%d %d", &N, &D) != EOF)45 {46 for (int i = 1; i <= N; i++)47 scanf("%d %d %d", k+i, e+i, p+i);48 scanf("%d", &G); getchar();49 memset(flag, 0, sizeof(flag));50 for (int i = 1; i <= G; i++){51 gets(str);52 int len = strlen(str);53 for (int j = 0; j < len;){54 if (str[j] >= ‘1‘ && str[j] <= ‘9‘){55 int sum = 0;56 while (str[j] >= ‘0‘ && str[j] <= ‘9‘){57 sum = sum * 10 + str[j] - ‘0‘;58 j++;59 }60 flag[sum] = i;61 }62 else j++;63 }64 }65 memset(dp, 128, sizeof(dp));66 oo = -dp[0];67 dp[0] = 0;68 for (int i = 1; i <= G; i++){69 memset(w[i], 128, sizeof(w[i]));70 w[i][0] = 0;71 }72 for (int i = 1; i <= N; i++){73 if (flag[i]){74 memset(tmp, 128, sizeof(tmp));75 tmp[0] = 0;76 }77 if (k[i] == 0 || k[i] * p[i] >= D)78 complete(p[i], e[i], flag[i] ? tmp : dp);79 else if (k[i] == 1){80 zero_one(p[i], e[i], flag[i] ? tmp : dp);81 }82 else{83 multi(p[i], e[i], k[i], flag[i] ? tmp : dp);84 }85 if (flag[i]) for (int j = 0; j <= D; j++) w[flag[i]][j] = max(w[flag[i]][j], tmp[j]);86 }87 for (int i = 1; i <= G; i++)88 for (int v = D; v >= 0; v--)89 for (int j = 0; j <= v; j++)90 if (dp[v-j] != -oo && w[i][j] != -oo){91 dp[v] = max(dp[v], dp[v-j] + w[i][j]);92 }93 if (dp[D] >= 0) printf("%d\n", dp[D]);94 else printf("i‘m sorry...\n");95 }96 return 0;97 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。