贪心算法-部分背包
有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，对应的价值是 v[i]。物品可以分割，求解将哪些物品装入背包，可使物品总价值最大，但是不能超过总容量。
【贪心策略】
每次选取单位重量价值（因为物品可分隔）最大的物品装入。
【输出描述】
输出两行。第一行输出可以装入背包的物品重量；第二行输出装入背包物品的总重量。
【输出样例】
10 30 50 25 35
170
【参考程序】
// 小牛编程
#include <bits/stdc++.h>
using namespace std;
//为了方便理解，使用了struct
struct product {
double w; //重量
double v; //价格
double u; //单位重量价值
};
product arr[10001]= {
{35, 10, 10/35},
{30, 40, 40/30},
{60, 30, 30/60},
{50, 50, 50/50},
{40, 35, 35/40},
{10, 40, 40/10},
{25, 30, 30/25}
};
bool cmp(product p1, product p2) {
return p1.u > p2.u;
}
int main() {
int n = 7;
double C = 150, wTotal = 0, vTotal = 0;
//单位重量价值降序排列
sort(arr, arr + n, cmp);
int i = 0;
while (i < n) {
if (wTotal + arr[i].w <= C) {
wTotal += arr[i].w;
vTotal += arr[i].v;
cout << arr[i].w << " ";
}
i++;
}
cout << endl << vTotal << endl;
return 0;
}