贪心法——部分背包问题

部分背包问题。有$n$个物体，第$i$个物体的重量为$w_i$，价值为$v_i$。在总重量不超过$C$的情况下让总价值尽量高。每一个物体都可以只取走一部分，价值和重量按比例计算。

和最优转载问题一样，这题也可以用贪心法解决。但是这题有两个因素，重量和价值，所以应该综合考虑两个因素。

直观的贪心策略是：优先拿性价比高的，也就是$\frac{v_i}{w_i}$大的，直到重量恰好为$C$。

由于可以拿部分，因此一定能保证重量恰好为$C$(除非$n$个物体总重量不足$C$)，并且除了拿的最后一个物体可能是拿部分以外，其他拿的都是拿整个。

部分背包问题算法实现

// 物体类型
struct Matter {// 重量float w;// 价值float v;// 从大到小排序bool operator < (const Matter &m) const {return (v / w) > (m.v / m.w);}
};// 贪心法
// 部分背包问题
void optionalLoad(Matter *m, int n, float C) {sort(m, m + n);float retain = C;float sumValue = 0;int i;for(i = 0; i < n; i++) {if(m[i].w <= retain) {cout << "第" << i + 1 << "个放入背包的重量为：" << m[i].w << "\t价值为：" << m[i].v << endl;retain -= m[i].w;sumValue += m[i].v;} else {if(retain != 0) {// 最后一个能放入重量的价值float retainValue = m[i].v / m[i].w * retain;cout << "第" << i + 1 << "个放入背包的重量为：" << retain << "\t价值为：" << retainValue << endl;sumValue += retainValue;}break;}}cout << "总价值为：" << sumValue << endl << endl;
}

测试主程序

#include <iostream>
#include <algorithm>using namespace std;// 物体类型
struct Matter {// 重量float w;// 价值float v;// 从大到小排序bool operator < (const Matter &m) const {return (v / w) > (m.v / m.w);}
};// 贪心法
// 部分背包问题
void optionalLoad(Matter *m, int n, float C) {sort(m, m + n);float retain = C;float sumValue = 0;int i;for(i = 0; i < n; i++) {if(m[i].w <= retain) {cout << "第" << i + 1 << "个放入背包的重量为：" << m[i].w << "\t价值为：" << m[i].v << endl;retain -= m[i].w;sumValue += m[i].v;} else {if(retain != 0) {// 最后一个能放入重量的价值float retainValue = m[i].v / m[i].w * retain;cout << "第" << i + 1 << "个放入背包的重量为：" << retain << "\t价值为：" << retainValue << endl;sumValue += retainValue;}break;}}cout << "总价值为：" << sumValue << endl << endl;
}int main() {while(true) {// n个物体int n;cout << "请输入物体总数(0退出)：";cin >> n;if(!n) {break;}float C;cout << "请输入不超过的总重量：";cin >> C;Matter m[n];for(int i = 0; i < n; i++) {cout << "第" << i + 1 << "个物体的重量、价值分别为：";cin >> m[i].w;cin >> m[i].v;}//cout << "总价值最高的组合和价值为：" << endl;optionalLoad(m, n, C);}return 0;
}

输出数据

请输入物体总数(0退出)：5
请输入不超过的总重量：10
第1个物体的重量、价值分别为：3 9
第2个物体的重量、价值分别为：9 3
第3个物体的重量、价值分别为：2 4
第4个物体的重量、价值分别为：4 2
第5个物体的重量、价值分别为：1 1
总价值最高的组合和价值为：
第1个放入背包的重量为：3        价值为：9
第2个放入背包的重量为：2        价值为：4
第3个放入背包的重量为：1        价值为：1
第4个放入背包的重量为：4        价值为：2
总价值为：16请输入物体总数(0退出)：5
请输入不超过的总重量：10
第1个物体的重量、价值分别为：2 3
第2个物体的重量、价值分别为：3 2
第3个物体的重量、价值分别为：6 1
第4个物体的重量、价值分别为：4 4
第5个物体的重量、价值分别为：5 1
总价值最高的组合和价值为：
第1个放入背包的重量为：2        价值为：3
第2个放入背包的重量为：4        价值为：4
第3个放入背包的重量为：3        价值为：2
第4个放入背包的重量为：1        价值为：0.2
总价值为：9.2请输入物体总数(0退出)：3
请输入不超过的总重量：9.2
第1个物体的重量、价值分别为：1 1
第2个物体的重量、价值分别为：2 2
第3个物体的重量、价值分别为：3 3
总价值最高的组合和价值为：
第1个放入背包的重量为：1        价值为：1
第2个放入背包的重量为：2        价值为：2
第3个放入背包的重量为：3        价值为：3
总价值为：6请输入物体总数(0退出)：0Process returned 0 (0x0)   execution time : 921.488 s
Press any key to continue.