Description

給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。
編程任務(wù)：
對(duì)于給定的n種物品和一個(gè)背包容量C，編程計(jì)算裝入背包中最大的物品總價(jià)值。

Input

輸入由多組測(cè)試數(shù)據(jù)組成。
每組測(cè)試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和C。正整數(shù)n是物品個(gè)數(shù)；正整數(shù)C是背包的容量。接下來(lái)的2行中，第一行有n個(gè)正整數(shù)，分別表示n個(gè)物品的重量，它們之間用空格分隔；第二行有n個(gè)正整數(shù)，分別表示n個(gè)物品的價(jià)值，它們之間用空格分隔。

Output

對(duì)應(yīng)每組輸入，輸出的每行是計(jì)算出的裝入背包中最大的物品總價(jià)值，保留一位有效數(shù)字。

Sample Input 

3 50
10 20 30
60 100 120

 

Sample Output 

240.0
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct Node 
{
    double weight;
    double value;    
};
bool comp (Node a,Node b)
{
    return a.value/a.weight > b.value/b.weight;
}
int main()
{
    int n,i;
    double c,w,v;
    while(scanf("%d%lf",&n,&c)!=EOF)
    {
        Node infor[2001];
        for(i=0;i<n;i++)
            scanf("%lf",&infor[i].weight);
        for(i=0;i<n;i++)
            scanf("%lf",&infor[i].value);
        sort(infor,infor+n,comp);    
        v = 0.0;
        w = 0.0;
        for(i=0;i<n;i++)
        {
            if(infor[i].weight + w <= c)
            {
                w += infor[i].weight;
                v += infor[i].value;
            } 
            else
            {
                v+=(c-w)/infor[i].weight * infor[i].value;
                break;
            }
        }
        printf("%.1lf\n",v);
    }
    return 0;
}