P1441 砝码称重
题目描述
现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。
输入输出格式
输入格式：
输入文件weight.in的第1行为有两个整数n和m，用空格分隔
第2行有n个正整数a1，a2，a3，……，an，表示每个砝码的重量。
输出格式：
输出文件weight.out仅包括1个整数，为最多能称量出的重量。
输入输出样例
输入样例#1：
3 11 2 2
输出样例#1：
3
说明
【样例说明】
在去掉一个重量为2的砝码后，能称量出1，2，3共3种重量。
【数据规模】
对于20%的数据，m=0；
对于50%的数据，m≤1；
对于50%的数据，n≤10；
对于100%的数据，n≤20，m≤4，m＜n，ai≤100。
这是福建省历届夏令营的题。。洛谷难度标签为提高+/省选-。。。
这道题刚看没有思路，但只要跟你讲这是dfs+dp就会有思路了。。
没错，这道题用dfs+dp。
dfs 用来搜索每一种舍弃m个砝码后， 还有什么砝码是剩下的。
dp用来求每一种舍弃m个砝码后，能量出种多少重量。
dp[j]表示重量为j时，能否量出j。最后答案dp[j]里有多少个true
相信大家已经心里有点底子了，看代码吧。
1 #include2 #include 3 4 int f[2005], ans, a[25]; 5 int m, n, tf[25]; 6 7 int Max(int _a, int _b) 8 { 9 return ((_a > _b) ? _a : _b);10 }11 12 void dp()13 {14 int ret, tot; //ret是表示这种舍弃的情况 能量出多少不同的重量15 memset(f, 0, sizeof(f)); //要记得每次重置。。。16 ret = tot = 0;17 f[0] = 1;18 for(int i=1; i<=n; i++)19 {20 if(tf[i]) continue; //如果这个砝码被舍弃了 就不考虑21 for(int j=tot; j>=0; j--)22 {23 if(f[j] && !f[j+a[i]]) //能量出j的重量 且j+a[i]的重量未被量(防止ret重复自增)24 {25 f[j+a[i]] = 1;26 ret++;27 }28 }29 tot += a[i]; //表示前i个(不包括i)砝码能量出的最大重量 30 //这样每次就可以直接从背包能表示的最大重量开始算 速度会快很多31 //(跟题解dalao学的)32 }33 ans = Max(ans, ret); //更新最大值34 }35 36 void dfs(int dep, int now) //dep是当前在考虑第dep个砝码 now为已经舍去的砝码数37 {38 if(now > m) return; //如果舍弃的砝码大于m39 if(dep > n+1) return; //如果考虑的砝码超过n。。40 if(dep == n+1) //如果考虑完了所有砝码41 {42 if(now < m) return; //如果舍弃的砝码小于m43 if(now == m) //考虑完所有砝码 且舍去了m个砝码 则dp()44 dp();45 }46 dfs(dep+1, now);47 tf[dep] = 1; 48 dfs(dep+1, now+1);49 tf[dep] = 0; //记得状态要调回来50 }51 52 int main()53 {54 scanf("%d%d", &n, &m);55 for(int i=1; i<=n; i++)56 scanf("%d", &a[i]);57 dfs(1,0);58 printf("%d", ans);59 return 0;60 }