问题:
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://www.cppblog.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]