题意：
给出n张牌的重量和现在剩下的牌的重量。
求缺失了的牌。
如果无解就输出0 多解就输出-1 否则就按照输入的顺序输出排的编号
思路：
01背包..
状态转移用dp[v] = cnt;表示牌的总和为v的情况是为cnt
记录路径有path[v] = j; 表示是加上了第j个物品才得到体积为v的。
一开始有一个已知的是dp[0] = 1;
状态转移方程为 if(dp[j-w[i]]) dp[j] += dp[j-w[i]]; 表示当前一个状态存在的情况下，这一个状态的情况数为前一个状态加上当前这个状态的情况数。
因为题目要求给出缺失的牌的编号，所以如果dp[j] == 0,即第一次遇到这个情况，就记录当前路径。主要是因为这个是空间优化的dp，用这个来标记的原因和01背包中第二层for循环从v循环到w[i]的理由一样，都是为了防止被后面的体积影响结果。
例如 第1 2 3个物体的体积是1 2 3， 而总的体积要求是6
因为1+2+3 = 6,所以路径理论上应该是1 2 3。但是当 j 为3,i 为 3即w[i] = 3的时候dp[j-w[i]] == 1
理论上这时候path[3] 应该 = 2; 即第一个物品的体积1加上第二个物品的体积2 = 3
但是因为正好有一件物品的体积为3，所以没有 if(dp[j] == 0) path[cnt++] = i;
这时候i = 3就会覆盖掉path[3]
但实际上最后path[6] 才应该是 = 3
最后如果dp[v] = 0代表无解 dp[v] > 1代表多解 ///其中v表示缺少的牌的总重量
如果dp[v] = 1; 则按path[j-path[j-path[...]]]找出路径，最后的最后就直接把路径输出。
Tips：
题目没有说明给出的数据关系，所以可以预处理的情况是如果现在有的牌的总重量为0，则所有牌都缺失了，这时候就把输入的牌全部输出，如果缺失的牌的体积比所有牌的体积和大，那肯定是无解的。
另外有一个要注意的地方是：要先处理现在有的牌的总重量为0的情况，因为dp的时候dp[0] 被初始化为1了，如果不先处理这种特殊情况，就会输出错误的答案。
Code：
View Code
1 #include <stdio.h> 2 #include <cstring> 3 #include <ctime> 4 #include <stdlib.h> 5 6 int main() 7 { 8 int n, v, cnt, tv, sum; 9 int w[110], dp[100010], path[100010], ans[110], vis[110]; 10 while(EOF != scanf("%d", &v)) { 11 memset(dp, 0, sizeof(dp)); 12 memset(vis, 0, sizeof(vis)); 13 memset(path, 0, sizeof(path)); 14 sum = cnt = 0; 15 scanf("%d", &n); 16 for(int i = 1; i <= n; ++i) { 17 scanf("%d", &w[i]); 18 sum += w[i]; 19 } 20 21 if(sum <= v) puts("0"); 22 else if(v == 0) { 23 for(int i = 1; i <= n; ++i) 24 printf("%d%c", i, i == n?'\n':' '); 25 } else { 26 v = sum-v; 27 dp[0] = 1; 28 for(int i = 1; i <= n; ++i) { 29 for(int j = v; j >= w[i]; --j) { 30 if(dp[j-w[i]] != 0) { 31 if(dp[j] == 0) path[j] = i; 32 dp[j] += dp[j-w[i]]; 33 } 34 } 35 } 36 37 if(dp[v] == 0) puts("0"); 38 else if(dp[v] > 1) puts("-1"); 39 else { 40 tv = v; 41 for(int i = path[tv]; tv > 0; i = path[tv]) { 42 ans[cnt++] = i; 43 tv -= w[i]; 44 } 45 for(int i = cnt-1; i >= 0; --i) 46 printf("%d%c", ans[i], i == 0?'\n':' '); 47 } 48 } 49 } 50 return 0; 51 }
题目链接：https://vijos.org/p/1071