背包问题
时间限制：3000 ms | 内存限制：65535 KB
难度：3
- 描述
- 现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
我为什么要说这个背包问题无语呢？看上文中红字，给的是单位重量的价值，而且每个物品可以分割，无语了吧。。。。
所以不需要用我博客里转载的那篇文章的算法，只要按每次放入最有价值的物品，一直到放不下就行了。再次无语。。。
#include
<iostream>02.#include
<algorithm>03.using namespace std;04. 05.#define
maxs 1206. 07.struct node08.{09.int v;10.int w;11.}good[maxs];12. 13.bool compare(const node
&a,const node
&b)14.{15.return a.v>b.v;16.}17. 18.int main()19.{20.int n,s,m,sum,i;21.cin>>n;22.while(n--)23.{24.cin>>s>>m;25.for(int i=0;i<s;i++)26.cin>>good[i].v>>good[i].w;27.sort(good,good+s,compare);28.sum=0;29.i=0;30.while(m)31.{32.if(good[i].w<=m)33.{34.sum+=good[i].v*good[i].w;35.m-=good[i].w;36.i++;37.}38.else39.{40.sum+=m*good[i].v;41.m=0;42.}43.}44.cout<<sum<<endl;45.}46.return 0;47.}