现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。
请注意，砝码只能放在其中一边。
对于20%的数据，m=0；
对于50%的数据，m≤1；
对于50%的数据，n≤10；
对于100%的数据，n≤20，m≤4，m＜n，ai≤100。
枚举不选的，然后01背包（如果用搜索就太慢了...）
思路不好想，代码好打
#include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int max(int a,int b) { return a>b ?a :b; } int n,m,tot; const int N=23; int d[N]; bool f[N]; int ans; bool ok[N*100]; void work() { memset(ok,false,sizeof(ok)); ok[0]=true; int nw=0; for(int i=1;i<=n;i++) { if(f[i]) continue; for(int j=tot-d[i];~j;j--) if(ok[j] && !ok[j+d[i]]) ok[j+d[i]]=true,nw++; } ans=max(ans,nw); } void dfs(int pos,int pre) { if(pos<0) { work(); return ; } int r=n-pos; for(int i=pre;i<=r;i++) { f[i]=true; dfs(pos-1,i+1); f[i]=false; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]),tot+=d[i]; dfs(m-1,1); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/xwww666666/p/11715762.html
