hdoj 2111 Saving HDU 【贪心】

小咪咪 2022-08-04 13:40 13阅读 0赞

# Saving HDU #

**Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 6921    Accepted Submission(s): 3193**

略

本题是贪心入门题，水水的；

思路：首先要对价值进行排序（笔者是按从大到小排的，若从小到大排也行），然后用背包剩余容量与当前第一个宝贝的体积进行比较，

① if 背包容量大于宝贝体积，这将宝贝纳入背包（用一个变量记录当前背包中宝贝的价值），然后接着用背包剩余容量与当前第一个宝贝进行比较，

② else 宝贝体积大于背包剩余容量，则取背包剩余容量同等体积的宝贝，计算价值，加入总价值；break；

已Accept代码(c++提交)

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    struct ak{
    	int s,c;
    }a[101];
    
    int cmp(ak x,ak y){		//从大到小排序 
    	return x.s>y.s;
    }
    
    int main(){
    	int n,v,i;
    	while(scanf("%d",&v),v){
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    			scanf("%d%d",&a[i].s,&a[i].c);
    		int val=0;				//记录背包中宝贝的总价值 
    		i=0;
    		sort(a,a+n,cmp);		//从大到小排序 
    		for(i=0;i<n;i++){
    			if(a[i].c>v){		//背包剩余容量与当前第一个宝贝体积比较 
    				val+=v*a[i].s;	//该情况是情况 ②
    				v=0;
    			}
    			else{				//该情况为情况 ①
    				v-=a[i].c;
    				val+=a[i].c*a[i].s;
    			}
    			if(v==0)
    				break;
    		}
    		printf("%d\n",val);
    	}
    	return 0;
    }

在写这篇博客时，正在看世锦赛男子4\*100米接力，看到中国夺银，太tm兴奋了，以上若有错误，请勿见怪，若发现错误，希望读者能主动给笔者留评论，谢谢!