题目描述
现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。
输入输出格式
输入格式：输入文件weight.in的第1行为有两个整数n和m，用空格分隔
第2行有n个正整数a1，a2，a3，……，an，表示每个砝码的重量。
输出格式：输出文件weight.out仅包括1个整数，为最多能称量出的重量。
输入输出样例
输入样例#1：
3 1 1 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。
/* 看到数据范围那么小，就直接暴力了，但是提高+/省选-的题怎么可能这么好做。。 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 25 using namespace std; int a[maxn],b[maxn],c[maxn],n,m,tot,ans,ansnow; bool vis[2010]; void count(int pos,int sum){ if(!vis[sum]&&sum!=0){ vis[sum]=1; ansnow++; } if(pos==tot+1)return; count(pos+1,sum); count(pos+1,sum+c[pos]); } void dfs(int pos,int cnt){ if(cnt==m){ memset(vis,0,sizeof(vis)); ansnow=0; int num=0; for(int i=1;i<=n;i++) if(b[i]!=-1)c[++num]=b[i]; count(1,0); ans=max(ans,ansnow); return; } if(pos==n+1)return; if(n-pos+1<m-cnt)return; dfs(pos+1,cnt);//不删掉 b[pos]=-1; dfs(pos+1,cnt+1); b[pos]=a[pos]; } int main(){ scanf("%d%d",&n,&m);tot=n-m; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } dfs(1,0); cout<<ans; }
/* 直接爆搜删去哪些砝码，统计方案数的时候用一个01背包就可以了 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 25 using namespace std; int a[maxn],b[maxn],c[maxn],n,m,tot,ans,ansnow,f[2010]; void count(){ memset(f,0,sizeof(f)); f[0]=1; for(int i=1;i<=n-m;i++) for(int j=2000;j>=c[i];j--) f[j]+=f[j-c[i]]; for(int i=1;i<=2000;i++) if(f[i])ansnow++; } void dfs(int pos,int cnt){ if(cnt==m){ ansnow=0; int num=0; for(int i=1;i<=n;i++) if(b[i]!=-1)c[++num]=b[i]; count(); ans=max(ans,ansnow); return; } if(pos==n+1)return; if(n-pos+1<m-cnt)return; dfs(pos+1,cnt);//不删掉 b[pos]=-1; dfs(pos+1,cnt+1); b[pos]=a[pos]; } int main(){ scanf("%d%d",&n,&m);tot=n-m; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } dfs(1,0); cout<<ans; }