問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1014思路:
1. 深度搜索
看到該題的第一個想法就是DFS，很快就寫出了代碼:
1 void
2 dfs(int *values, int index, long cur_value_sum)
3 {
4 if(cur_value_sum >= value_half) {
5 if(cur_value_sum == value_half)
6 flag = 1;
7 return;
8 }
9 if(index < 1)
10 return;
11 int i;
12 for(i=values[index]; i>=0 && (!flag); i--) {
13 cur_value_sum += (i*index);
14 dfs(values, index-1, cur_value_sum);
15 cur_value_sum -= (i*index);
16 }
17 }
額...結果TLE...
仔細看題，發現maximum total number will be 20000, 所以超時幾乎是肯定的
其實，discuss里有人用DFS+Cut通過的，只是自己太菜，還不會減枝
2. 動態規劃
2.1 from: http://m.shnenglu.com/AClayton/archive/2007/09/14/32185.html聲明數組can_reach[60005]
can_reach[i]=1, 表示存在一個人獲得價值為 i ,另一個人獲得價值為value_sum-i的方案
我們的目標就是要確定can_reach[value_sum>>1]是否等于1
1 int
2 dp()
3 {
4 int i, j, k, temp, cur_max = 0;
5 can_reach[0] = 1;
6 for(i=1; i<=VALUE_MAX; i++) {
7 if(num[i] > 0) {
8 for(j=cur_max; j>=0; j--) { /* tricky, pay attention */
9 if(can_reach[j]) {
10 for(k=1; k<=num[i]; k++) {
11 temp = i*k+j;
12 if(temp == value_half)
13 return 1;
14 if(temp>value_half) /* initial: if(temp>value_half || can_reach[temp]) break; */
15 break;
16 can_reach[temp] = 1;
17 }
18 }
19 }
20 }
21 cur_max += (i*num[i]);
22 if(cur_max>value_half)
23 cur_max = value_half;
24 }
25 }
注意: 上述代碼的第14行，原文中存在減枝，但沒有看懂，所以沒有放進去，還好，該代碼還是AC了
2.2 from:
http://blog.sina.com.cn/s/blog_5c95cb070100cvt8.html該問題可以轉化成一個0-1背包模型(見：背包九講)
關鍵是下面的數論知識:
對于任意一個正整數 n, 它可以表示成:
n = 1 + 1<<1 + 1<<2 + ... + 1<<k + res[余數]
我們可以得到：對于1<=i<=n的任意正整數 i, 它肯定可以表示成: 1, 1<<1, 1<<2, ... 1<<k, res的一個組合
因此，對于該題，我們可以對輸入做預處理:
1 len = 0;
2 memset(value_weight, 0, sizeof(value_weight));
3 for(i=1; i<=VALUE; i++) {
4 if(num[i] != 0) {
5 j = 0;
6 while((1<<(j+1)) <= (num[i]+1)) {
7 value_weight[len++] = i*(1<<j);
8 ++j;
9 }
10 if((num[i]+1-(1<<j))>0)
11 value_weight[len++] = i*(num[i]+1-(1<<j));
12 }
13 }
接下來，原問題就轉化成:
背包容量value_half(value_sum/2)，每件物品的cost與value都是value_weight[i]，考慮是否存在一種方案，使得總價值等于value_half
0-1背包的典型DP狀態方程:
f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+v[i]), f[i][j]表示前i件物品放入容量為j的背包而可以獲得的最大價值
1 int
2 knapsack()
3 {
4 int i, w, pre, cur;
5 memset(table, 0, sizeof(table));
6 for(w=value_weight[0]; w<=value_half; w++) {
7 table[0][w] = value_weight[0];
8 if(table[0][w] == value_half)
9 return 1;
10 }
11 for(i=1; i<len; i++) {
12 cur = i%2;
13 pre = (i+1)%2;
14 for(w=0; w<=value_half; w++) {
15 if(w>=value_weight[i])
16 table[cur][w] = max(table[pre][w], table[pre][w-value_weight[i]]+value_weight[i]);
17 else
18 table[cur][w] = table[pre][w];
19 if(table[cur][w] == value_half)
20 return 1;
21 }
22 }
23 return 0;
24 }
AC [ Memory: 836K, Time: 16MS]