2023年8月1日发(作者：)

可拆分背包问题（贪⼼算法）描述： 这⾥有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 #includeusing namespace std;//需要⼀个结构体，通过性价⽐，能够查找到重量和价值。//做⼀个排序，需要将性价⽐由⾼到底排序，排序的过程中重量和（价值）要对应上typedef struct { double aver; double w; double v;}Knapsack;bool cmp(Knapsack a, Knapsack b){ return > ;}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;}

2023年8月1日发(作者：)

可拆分背包问题（贪⼼算法）描述： 这⾥有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 #includeusing namespace std;//需要⼀个结构体，通过性价⽐，能够查找到重量和价值。//做⼀个排序，需要将性价⽐由⾼到底排序，排序的过程中重量和（价值）要对应上typedef struct { double aver; double w; double v;}Knapsack;bool cmp(Knapsack a, Knapsack b){ return > ;}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;}