CodeVS/2144

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
砝码称重 2	★★☆☆☆	答案正确	100	2015-2-3 22:46:13	无

题意

n个砝码凑齐总重量m，每个砝码至多用一次，问最少砝码数。

题解

• 一开始愣了一下还去想贪心，和CodeVS/1099异曲同工，也是双向搜索+哈希/map解决。

代码

2144.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<map> #include<iostream> #include<climits> using namespace std; map<int,int> ans; int n,m; int w[1000]={},Ans=INT_MAX; void dfs(const int &_index,const int &_weight,const int &_count) { if(_index>(n>>1)+1) return; if(ans.count(_weight)) ans[_weight]=min(ans[_weight],_count); else ans[_weight]=_count; dfs(_index+1,_weight+w[_index],_count+1); dfs(_index+1,_weight,_count); } void rdfs(const int &_index,const int &_weight,const int &_count) { if(_index<(n>>1)) return; if(ans.count(m-_weight)) Ans=min(ans[m-_weight]+_count,Ans); rdfs(_index-1,_weight+w[_index],_count+1); rdfs(_index-1,_weight,_count); } int main() { cin>>n>>m; for(int i=1;i<=n;++i) cin>>w[i]; dfs(1,0,0); rdfs(n,0,0); cout<<Ans; return 0; }