求教用map实现一个类似背包的问题
  • 板块学术版
  • 楼主Yusani_huh
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/5/26 23:00
  • 上次更新2023/11/7 01:39:54
查看原帖
求教用map实现一个类似背包的问题
239895
Yusani_huh楼主2020/5/26 23:00

先请不要告诉我标题所述的方法是否可行,请问如下的代码哪里出锅了?(如果此方法根本上就行不通那当我没提问)

我第一次用 map 做这种类型,不知道是哪里出锅,如有低级错误烦请见谅...(毕竟之前也不是没有犯过)

大致的意思是:有 nn 件物品和 mm 元钱,给出这些物品的价格,问能否刚好凑出 mm 元。

#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

2020/5/26 23:00
加载中...