poj 1014 Dividing 多重背包

Dividing

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 49825		Accepted: 12552

Description

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.

Input

Each line in the input file describes one collection of marbles to be divided. The lines contain six non-negative integers n1 , . . . , n6 , where ni is the number of marbles of value i. So, the example from above would be described by the input-line "1 0 1 2 0 0". The maximum total number of marbles will be 20000.
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.

Output

For each collection, output "Collection #k:", where k is the number of the test case, and then either "Can be divided." or "Can't be divided.".
Output a blank line after each test case.

Sample Input

1 0 1 2 0 0 
1 0 0 0 1 1 
0 0 0 0 0 0

Sample Output

Collection #1:
Can't be divided.

Collection #2:
Can be divided.


这就是所谓的多重背包。按照标准的板子写的，思路是转化为01背包和完全背包，并且运用二进制优化，复杂度是V*log(Mi)。先计算出sum/2，因为两人要平均分，所以要看这个容量为sum/2的背包是不是可以被装满，每件物品的价值是1。先把除f[0]外的其它值赋值为负无穷大，最后判断f[V]的值是不是大于0.
注意：不能判断是不是等于ＭＡＸ，因为显然Ｆ［Ｖ］已经的值修改了。

没看别人的代码，完全照着背包九讲里面的伪代码写的。还是有一点儿成就感，和照着别人的代码写出来感觉完全不一样。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 using namespace std;
 7 int f[120000+10], V;
 8 const int MAX = 0x3f3f3f3f;
 9 void zeropack(int c, int w){
10   for (int v = V; v >= c; --v){
11     f[v] = max(f[v], f[v-c] + w);
12   }
13 }
14 void completepack(int c, int w){
15   for (int v = c; v <= V; ++v){
16     f[v] = max(f[v], f[v-c] + w);
17   }
18 }
19 int main(void){
20   int a[7], cnt = 1;
21 #ifndef ONLINE_JUDGE
22   freopen("1014.in", "r", stdin);
23 #endif
24   while (~scanf("%d", a)){
25     int sum = a[0]; a[1] = a[0];
26     for (int i = 2;i < 7; ++i) {
27       scanf("%d", a+i); sum += a[i]*i;
28     }
29     if (sum==0) break;
30     printf("Collection #%d:\n", cnt); cnt++;
31     if (sum&1){
32       printf("Can't be divided.\n\n");
33       continue;
34     }
35     V = sum/2;
36     f[0] = 0; for (int i = 1; i < 120000; ++i) f[i] = -MAX;
37     for (int i = 1; i <= 6; ++i){
38       if (i*a[i] >= V){
39         completepack(i, 1);
40       }
41       else{
42         int k = 1; 
43         while (k < a[i]){
44           zeropack(i*k, 1*k); a[i] -= k; k *= 2;
45         }
46         zeropack(i*a[i], 1*a[i]);
47       }
48     }
49     if (f[V] < 0) printf("Can't be divided.\n");
50     else printf("Can be divided.\n");
51     printf("\n");
52   }
53   return 0;
54 }

这题以前做过，当初抄的别人的代码，明显是人家的代码效率更高……

 1 # include <stdio.h>
 2 # include <stdlib.h>
 3 # include <string.h>
 4 
 5 int dp[20000*6];
 6 int num[20000*6];
 7 
 8 int main(void)
 9 {
10     int t, a[10], i, sum, j;
11 
12 //    freopen("poj.in", "r", stdin);
13     t = 1;
14     while (scanf("%d", &a[1]) != EOF)
15     {
16         sum = a[1];
17         for (i = 2; i < 7; i++)
18         {
19             scanf("%d", &a[i]);
20             sum += a[i] * i;
21         }
22         if (sum == 0)
23         {
24             break;
25         }
26         printf("Collection #%d:\n", t);
27         t++;
28         if (sum % 2)
29         {
30             printf("Can't be divided.\n\n");
31             continue;
32         }
33         else
34         {
35             sum /= 2;
36             memset(dp, 0, sizeof(dp));
37             dp[0] = 1;
38             for (i = 1; i < 7; i++)
39             {
40                 memset(num, 0, sizeof(num));
41                 for (j = i; j < sum + 1; j++)
42                 {
43                     if (!dp[j] && dp[j-i] && num[j-i] < a[i])
44                     {
45                         dp[j] = 1;
46                         num[j] = num[j-i] + 1;
47                     }
48                 }
49                 if (dp[sum])
50                 {
51                     break;
52                 }
53             }
54             if (dp[sum])
55             {
56                 printf("Can be divided.\n\n");
57             }
58             else
59             {
60                 printf("Can't be divided.\n\n");
61             }
62         }
63     }
64 
65     return 0;
66 }

没看懂有木有……显然比我的思路巧妙多了。。看到中间那几行核心代码，联想到了楼教主的男人八题里面的一道，貌似，，以后有时间看一下！这个代码再认真研究一下！

题外话：有些事不多说了，说多了都是泪……别胡思乱想了，好好奋斗吧，哈哈。