简答题 偏难
#7093

圣诞老人的礼物 圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的…

圣诞老人的礼物

圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果,请问圣诞老人最多能带走多大价值的糖果。

时间限制:1000

内存限制:65536

输入

第一行由两个部分组成,分别为糖果箱数正整数n(1 = n = 100),驯鹿能承受的最大重量正整数w(0<w<10000),两个数用空格隔开。其余n行每行对应一箱糖果,由两部分组成,分别为一箱糖果的价值正整数v和重量正整数w,中间用空格隔开。

输出

输出圣诞老人能带走的糖果的最大总价值,保留1位小数。输出为一行,以换行符结束。

样例输入

4 15
100 4
412 8
266 7
591 2

样例输出

1193.0
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; using namespace std; struct gift {   int value;   int weight;   double density; } gf[101]; bool cmp(gift f1, gift f2) { // 按照单重价值从大到小排序   return f1.density &gt; f2.density; } int main() {   int n, w;   cin &gt;&gt; n &gt;&gt; w;   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; gf[i].value &gt;&gt; gf[i].weight;     gf[i].density = 1.0 * gf[i].value / gf[i].weight;   }   sort(gf, gf + n, cmp);   double totw = 0, totv = 0; // 注意到w为int型,可拆分为double型   // 所以新建一个double型保存背包剩余重量   for (int i = 0; i &lt; n; i++) {     if (totw + gf[i].weight &lt;= w) {       totw += gf[i].weight;       totv += gf[i].value;     } else {       totv += gf[i].density * (w - totw);       totw = w;       break;     }   }   printf("%.1lf", totv);   return 0; }</pre>
这道题暂未补解析。