文章

49

粉丝

140

获赞

27

访问

16.8k

头像
简单背包问题 题解:贪心算法
P1035
发布于2024年2月5日 18:09
阅读数 484

#include <iostream>
using namespace std;
int main(){

	int weigh=0,n=0,index=0;
	int a[10000];
	while(cin >>weigh){
		cin >>n;
		for(int i=0;i<n;i++)
			cin >> a[i];
		//冒泡排序  降序==================================
		for(int i=0;i<n;i++)
			for(int j=n-2;j>=i;j--)
			{
				if(a[j+1]>a[j]){
					index=a[j+1];
				a[j+1]=a[j];
				a[j]=index;}
			}
		for(int i=0;i<n&&weigh>0;){
			if(weigh-a[i]>=0)
				weigh=weigh-a[i];
			else
				i++;//只能往后找
		}
		if(weigh==0)
			cout <<"YES" <<endl;
		else//weigh >0的情况
			cout <<"NO" <<endl;
	}
	system("pause");
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发