首页 > 代码库 > 2144 砝码称重 2
2144 砝码称重 2
2144 砝码称重 2
时间限制: 1 s
空间限制: 16000 KB
题目等级 : 钻石 Diamond
题目描述 Description
有n个砝码，现在要称一个质量为m的物体，请问最少需要挑出几个砝码来称？
注意一个砝码最多只能挑一次
输入描述 Input Description
第一行两个整数n和m，接下来n行每行一个整数表示每个砝码的重量。
输出描述 Output Description
输出选择的砝码的总数k，你的程序必须使得k尽量的小。
样例输入 Sample Input
3 10
5
9
1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
1<=n<=30，1<=m<=2^31，1<=每个砝码的质量<=2^30
分类标签 Tags 点此展开
哈希表 线性结构
题解：
hash？？
还是爆搜吧；
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int N=1000;#define ll long longll n,m,w[N],sum[N];int dfs(int i,ll s){ int min=0,k; ll t; for(int j=i;j>=0;j--){ if(s+sum[j]<m) break;//不能更小，剪枝 t=s+w[j]; if(t<m){ k=dfs(j-1,t); if(k!=0&&(min==0||min>k+1)) min=k+1;//取小 } else if(t==m) return 1;//搜到答案 } return min;}int main(){ cin>>n>>m; for(int i=0;i<n;i++) cin>>w[i]; sort(w,w+n); sum[0]=w[0]; for(int i=1;i<n;i++) sum[i]=sum[i-1]+w[i]; printf("%d",dfs(n-1,0));}
2144 砝码称重 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。