题目描述 Description
有n个砝码，现在要称一个质量为m的物体，请问最少需要挑出几个砝码来称？
注意一个砝码最多只能挑一次
输入描述 Input Description
第一行两个整数n和m，接下来n行每行一个整数表示每个砝码的重量。
输出描述 Output Description
输出选择的砝码的总数k，你的程序必须使得k尽量的小。
样例输入 Sample Input
3 10
5
9
1
样例输出 Sample Output
数据范围及提示 Data Size & Hint
1<=n<=30，1<=m<=2^31，1<=每个砝码的质量<=2^30
【思路】
正解：搜索
神正解：双向搜索
吐槽：你都知道质量是m了你称个鬼啊╭(╯^╰)╮
【code】
我的智障搜索
#include<iostream>
#include<cstdio>
using namespace std;
int w[],use[];
long long ans,m;
int n,res=;
void dfs(int x)
{
if(ans>=res){
return;
}
if(!m)
{
if(ans<res)
res=ans;
return ;
}
for(int i=;i<=n;i++)
{
if(!use[i]&&w[i]<=m)
{
use[i]=;
m-=w[i];
ans++;
dfs(x+);
m+=w[i];
use[i]=;
ans--;
}
}
return;
}
int main()
{
scanf("%d%lld",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&w[i]);
dfs();
printf("%d\n",res);
return ;
}
比较尴尬.....
用后缀和优化 剪枝
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long w[],last[];
int n,m;
int ans;
inline int read()
{
int f=,x=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
inline bool cmp(int a,int b)
{
return a>b;
}
inline void dfs(int now,int use,long long ww)
{
if(use>=ans)return;
if(ww==m){ans=min(ans,use);}
for(int i=now+;i<=n;i++)
{
if(ww+last[i]<m)return;
if(ww+w[i]>m)continue;
dfs(i,use+,ww+w[i]);
}
return;
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)
w[i]=read();
sort(w+,w+n+,cmp);
for(int i=n;i>=;i--)
last[i]=last[i+]+w[i];
ans=n;
dfs(,,);
printf("%d\n",ans);
return ;
}
发现加上inline也没多大用。（前后对比）
比较神的双向搜索，其实我做这个题就是为了学这个方法。
就是把原来的数分成两部分进行dfs。
并用map<int,int>这些质量需要多少砝码。
mm-sum能在第一次dfs中能找到。（sum表示第二次dfs中目前总质量）
js+m[mm-sum];来更新最优解。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int ans(),w[],n;
long long mm;
map<int, int>m;
void dfs(int js,int last,int sum,bool k)
{
int r=n;
if(k){m[sum]=js;r/=;}
else
{
if(m.find(mm - sum)!=m.end())
ans=min(ans,js+m[mm-sum]);
}
for(int i=last;i<r;i++)
dfs(js+,i+,sum+w[i],k);
}
int main()
{
scanf("%d%lld",&n,&mm);
for(int i=;i<n;i++)
scanf("%d",&w[i]);
dfs(,,,true);
dfs(,n/,,false);
printf("%d\n",ans);
return ;
}