Description

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。
編程任務：
對于給定的n種物品和一個背包容量C，編程計算裝入背包中最大的物品總價值。

Input

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

Output

對應每組輸入，輸出的每行是計算出的裝入背包中最大的物品總價值，保留一位有效數字。

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;
}