背包问题-1(贪心)

冷不防 2022-04-05 10:13 194阅读 0赞

###  ###

题目描述

已知有一个可容纳重量为C的背包以及n件物品，其中第i件物品的重量为wi，每件物品的价值为pi（pi>0）。怎样向背包装如物品，才能使装入背包的物品的价值最大，编程求出最大价值（一件物品可以部分装入，部分装入是要合理、近似的装入，除不尽时，保留两位小数）。

输入

物品件数n

背包容量C

每件物品的重量和价值

输出

最大价值

样例输入

3  
30  
20 40  
15 25  
15 25

样例输出

56.66

##### 分析： #####

本题，是典型的贪心问题。因为可以近似的装入。所以，我们需要考虑的是每一个单位重的物品的对应的价值。即15 25 这个物品的每一个单位重的价值是25/15。所以我们需要做的是将这些物品按照每一个单位重的价值进行降序排序。  
代码如下：

#include"stdio.h"
    #include"string.h"
    int main()
    {
        int C,n;
        int w[1000],p[1000];
        int i,j,k,t;
        double P;
        while(~scanf("%d%d",&n,&C))
        {
            for(i=0;i<n;i++)
                  scanf("%d%d",&w[i],&p[i]);
            for(i=0;i<n-1;i++)
               for(j=i;j<n;j++)
                   if((double)p[i]/w[i]<(double)p[j]/w[j])
            {
                t=p[i];p[i]=p[j];p[j]=t;
                t=w[i];w[i]=w[j];w[j]=t;
            }
            i=0;P=0;
            while(i<n)
            {
                if(C>=w[i])
                {
                    P=P+p[i];
                    C=C-w[i];//C要不断减
                }
                else
                    {P=P+(double)p[i]/w[i]*C;
                     C=0;break;
                    }
                i++;
                if(C==0)
                     break;
            }
         printf("%0.2lf\n",(int)(P*100)/100.0);
        }
    }