题目描述
现有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。
思路
题目很简单,但有一种十分方便的写法,用二进制代替背包。将原来的背包改为b|b<<w[j]最后统计1的个数即可完成。对于原来的每一种状态假设b的第i位为1,b<<w[j]后b的第i + w[j]位变为了1,表示重量i + w[j]可被称出,因此可以使代码更简单。
代码
#include<bits/stdc++.h> using namespace std; int m,n,ans=0; int w[27]; int pp(int x){ int cnt=0; for(int j=0;j<n;j++) if(x&(1<<j)) cnt++; return cnt; } int main() { cin>>n>>m; for(int i=0;i<n;i++)cin>>w[i]; for(int i=1;i<1<<n;i++){ if(pp(i)==n-m){ bitset<2019> b; b[0]=1; for(int j=0;j<n;j++) if(i&(1<<j)) b|=b<<w[j]; int len=b.count(); ans=max(ans,len-1); } } cout<<ans<<endl; return 0; }