题目:有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
思路:
让你把物品一个个的往包里装,要求装入包中的物品总价值最大,要让总价值最大,就可以想到怎么放一个个的物品才能让总的价值最大,因此可以想到如下三种选择物品的方法,即可能的局部最优解:
①:每次都选择价值最高的往包里放。
②:每次都选择重量最小的往包里放。
③:每次都选择单位重量价值最高的往包里放。
找到可能的局部解以后,分析每一种解能不能合起来变成总体最优解,对以上三中局部解一一分析:
①:选择价值最高的,就会忽略了重量,若
M=50,
物品1: 重量:50,价值:40
物品2: 重量:20,价值30
物品3: 重量:30,价值30
显然,对于上述情况,该局部解行不通。
②:选择重量最小的,就会忽略了价值,同①策略类似。
③:该策略总是能让装入包中的物品总价值最大,所以该策略是正确的贪心策略。
注:(http://blog.csdn.net/a925907195/article/details/41314549该篇博客说第三种情况在一下情况是错的,
物品:A B C
重量:28 20 10
价值:28 20 10
其实该情况是符合贪心策略的,因为该总情况不管先选哪两个都会把背包塞满,因为该题物品可以分割成任意大小,所以,就算空下一下,也可以将最 后一个物品分割,放进去,它们 的单位重量的价值是一样的,所以,最后背包最后重量相同,重量相同那么价值也相同。)
所以采用第三种策略,代码如下:
#include#include using namespace std; struct bag{ int weight; int value; float bi; float bili; }bags[100]; bool compare(const bag &bag1,const bag &bag2); int main() { int sum=0,n; float M; int j=0; cout<<"输入背包容量和物品种类数量:"< >M>>n; for(int i=0;i >bags[i].weight>>bags[i].value; bags[i].bi=bags[i].weight/bags[i].value; } for(int i=0;i bag2.bi; }
C++知识点总结:
①使用sort()函数需要在开头写,#include
②使用sort()比较结构体数组:
bool compare(const bag &bag1,const bag &bag2){ return bag1.bi>bag2.bi; }