苹果(背包)

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int bag[1001];
struct Case{
    int c,w;
}apple[1010];
/*int cmp(Case a,Case b){
    return (1.0*a.w/a.c)>(1.0*b.w/b.c);
}*/
int main(){
    int n,v;
    while(scanf("%d%d",&n,&v),n||v){memset(bag,0,sizeof(bag));
        for(int i=0;i<n;++i)scanf("%d%d",&apple[i].c,&apple[i].w);
        /*sort(apple,apple+n,cmp);*/
        for(int i=0;i<n;++i){ //printf("%d ",apple[i].c);
            for(int j=v;j>=apple[i].c;j--)if(bag[j-apple[i].c]+apple[i].w>bag[j])bag[j]=bag[j-apple[i].c]+apple[i].w;
        }
        printf("%d\n",bag[v]);
    }
    return 0;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。