描述
现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
输入
第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。
输出
输出每组测试数据中背包内的物品的价值和，每次输出占一行。
样例输入
1 3 15 5 10 2 8 3 9
样例输出
65
代码
#include<iostream> #include<algorithm> #include<vector> using namespace std; bool cmp(pair<int,int>a,pair<int,int>b){ return a.first > b.first; } int main(){ int n; vector< pair<int, int> > good; cin >> n; while(n--){ int s, m,v,w; cin >> s >> m; //初始化 good.clear(); int sv = 0; //读入数据 for(int i = 0; i < s; i++){ cin >> v >> w; good.push_back(make_pair<int,int>(v,w)); } //排序由大至小 sort(good.begin(),good.end(),cmp); //贪心选择 for(int i = 0; i < good.size() && m; i++){ if(good[i].second <= m){ sv += good[i].first*good[i].second; m -= good[i].second; } else{ sv += good[i].first*m; m = 0; } } //输出结果 cout << sv << endl; } return 0; }