杭電 2111 Saving HDU 貪心算法 背包問題 -开发者知识库

杭電 2111 Saving HDU 貪心算法 背包問題 -开发者知识库,第1张

Saving HDU

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6727    Accepted Submission(s): 3093


Problem Description 話說上回講到海東集團面臨內外交困,公司的元老也只剩下XHD夫婦二人了。顯然,作為多年拼搏的商人,XHD不會坐以待斃的。
  一天,當他正在苦思冥想解困良策的時候,突然想到了自己的傳家寶,那是公司成立的時候,父親作為賀禮送來的一個錦囊,徐父當時交代,不到萬不得已的時候,不要打開它。“現在不正是最需要的時候嗎?”,一邊想,XHD一邊找到了這個精心保管的錦囊,打開一看,里面只有一句話“杭城北麓千人洞有寶”。
  二話不說,XHD拿起一個大口袋就出發了,這個千人洞他是知道的,小的時候,爸爸曾經帶他來過這個隱蔽的路口,並告訴他,這是千人洞。他現在才明白爸爸當初這句話的含義。
  盡管有點印象,XHD還是花了很大的精力才找到這個異常隱蔽的洞口,走進一看,幾乎驚呆了,真的是眼花繚亂!不過盡管寶貝的種類不少,但是每種寶貝的量並不多,當然,每種寶貝單位體積的價格也不一樣,為了挽救HDU,現在請你幫忙盡快計算出來XHD最多能帶回多少價值的寶貝?(假設寶貝可以分割,分割后的價值和對應的體積成正比)
 


 

Input 輸入包含多個測試實例,每個實例的第一行是兩個整數v和n(v,n<100),分別表示口袋的容量和寶貝的種類,接着的n行每行包含2個整數pi和mi(0<pi,mi<10),分別表示某種寶貝的單價和對應的體積,v為0的時候結束輸入。
 


 

Output 對於每個測試實例,請輸出XHD最多能取回多少價值的寶貝,每個實例的輸出占一行。
 


 

Sample Input
2 2
3 1
2 3
0
 


 

Sample Output
5



經過錦囊相助,HDU會脫離危機嗎?
欲知后事如何,且聽下回分解——
 

很簡單的一道題,普通的貪心。

#include<stdio.h>
#include<algorithm>
using namespace std;

struct node{
int p;
int v;
}m[110];

int cmp(node a,node b){
if(a.p==b.p) return a.v<b.v;
return a.p>b.p;
}

int main(){
int v,n;
while(~scanf("%d",&v)&&v){
scanf("%d",&n);
int i=0;
for(i=0;i<n;i ){
scanf("%d%d",&m[i].p,&m[i].v);
}
sort(m,m n,cmp);
int sum=0;
for(i=0;i<n;i ){
if(v>m[i].v){
sum =m[i].p*m[i].v;
v=v-m[i].v;
continue;
}
if(v<=m[i].v){
sum =m[i].p*v;
break;
}
}
printf("%d\n",sum);
}
return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复