描述:
这里有n种不同值v[i]和权重w[i]的对象(如果选择该对象的w[i]可以获得值v[i])。
你有一个容器来挑选它们。你可以根据自己的需要把它们分成任意大小的碎片。可以拾取的对象的最大重量给定为w。请计算您能得到的最大值。
输入:
第一行输入n W(0<=n<=1000)(0<=W<=10000)
第二行输入n个物品的价值(0<=v[i]<=10000)
第三行输入n个物品的质量(0<=w[i]<=10000)
输出:
最大的价值,保留三位小数。
分析:
本题跟传统的0-1背包问题不同,本题中的物体可以分成任意份,所以我们可以运用贪心算法,根据物品的性价比(价值 / 质量)来解题,根据性价比的高低依次将物体放入背包中,当物体不能完全放入背包时,总价值 = 完全放入物品的价值 + 背包剩余空间 * 接下来应放入背包物品的性价比。
代码:
#include#include #include using namespace std; //需要一个结构体,通过性价比,能够查找到重量和价值。 //做一个排序,需要将性价比由高到底排序,排序的过程中重量和(价值)要对应上 typedef struct { double aver; double w; double v; }Knapsack; bool cmp(Knapsack a, Knapsack b) { return a.aver > b.aver; } int main() { Knapsack arrays[1009]; int n; double m; double V = 0; cin >> n >> m; for (int i = 0; i < n; i++) cin >> arrays[i].v; for (int i = 0; i < n; i++) cin >> arrays[i].w; //求性价比 for (int i = 0; i < n; i++) { arrays[i].aver = arrays[i].v / arrays[i].w; //cout << arrays[i].aver << endl; } //性价比排序 sort(arrays, arrays + n, cmp); int sum = 0; for (int i = 0; i < n; i++) //当背包能装下所有物品时,直接输出所有的物品价值之和 { sum += arrays[i].w; } if (sum < m) { for (int j = 0; j < n; j++) V += arrays[j].v; //V = floor(V * 1000.0) / 1000.0; cout << setiosflags(ios::fixed) << setprecision(3) << V << endl; return 0; } //应该由性价比的顺序,通过容量,选择装入的物品 for (int i = 0; i < n; i++) { if (arrays[i].w <= m) { V = V + arrays[i].v; m = m - arrays[i].w; } else {//直接将剩余的m加入即可 V = V + m * arrays[i].aver; m = 0; } if (m == 0) break; } //V = floor(V * 1000.0) / 1000.0; cout << setiosflags(ios::fixed) << setprecision(3) << V << endl; return 0; }