先请不要告诉我标题所述的方法是否可行,请问如下的代码哪里出锅了?(如果此方法根本上就行不通那当我没提问)
我第一次用 map 做这种类型,不知道是哪里出锅,如有低级错误烦请见谅...(毕竟之前也不是没有犯过)
大致的意思是:有 n 件物品和 m 元钱,给出这些物品的价格,问能否刚好凑出 m 元。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[43];
map<int,bool>h;
int main(){
while(scanf("%d%d",&n,&m)){
h.erase(h.begin(),h.end()); //多组数据先清空
h[0]=true;
bool fl=false;
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
int e=h.end()->first;
for(map<int,bool>::iterator it=h.begin();it->first<e;it++){ //因为做的是背包所以加了这么一个奇怪的判定
int sum=(it->first)+a[i];
if(sum==m){ //如果已经达到所需金额
fl=true;
printf("YES\n");
break;
}
h[sum]=true;
}
if(fl) break;
}
if(!fl) printf("NO\n"); //如果flag不为true则没有达到
}
return 0;
}
有时候输出的就是错误答案,有时候会多次输出YES
或者NO
。