[已解决]贪心算法（背包问题），有点瑕疵，求解！

°﹍M、Sulayman

重量设置在150，应该判断4次，第五次重量就到190了，结果程序输出第五次结果......郁闷

1. '''
   
2.                         贪心算法
   
3. 
   
4. 需求：
   
5.     有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
   
6.     要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
   
7. '''
   
8. 
   
9. goods = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
   
10. weight = [35, 30, 60, 50, 40, 10, 25]
    
11. price = [10, 40, 30, 50, 35, 40, 30]
    
12. 
    
13. count = 1
    
14. sumWeight = 0
    
15. BagSet = []
    
16. 
    
17. print('每次挑选物品中价值最大的物品装入背包。')
    
18. 
    
19. while True:
    
20. 
    
21.     if sumWeight <= 150:
    
22. 
    
23.         ChoPri = max(price)
    
24.         flag_ChoPri = price.index(ChoPri)
    
25.         sumWeight += weight[flag_ChoPri]
    
26.         ChoGoods = goods[flag_ChoPri]
    
27.         BagSet.append(ChoGoods)
    
28.         price[flag_ChoPri] = 0
    
29.         print('第%s次挑选过后' % count)
    
30.         count += 1
    
31.         print('此时背包的重量为%s。' % sumWeight)
    
32.         print('此时背包里面的物品有:')
    
33.         print(BagSet)
    
34.         print('---------------------------')
    
35. 
    
36.     else:
    
37. 
    
38.         print('贪心也要有个度！')
    
39.         break
    

复制代码

最佳答案

月排行榜 / 总排行榜

wei_Y

2016-10-24 21:22:00

°﹍M、Sulayman 发表于 2016-10-24 21:19
必    输出第五次！？~

说着玩的，见谅。

感觉建表时用字典好些？

somethings = {'A': [weight. price]}

使用列表然后index这种方法对有重复的数据时会出现很大的不准确性。

跳转到最佳答案楼层

wei_Y

无解。

°﹍M、Sulayman

这是基于不分割，每次挑选此刻物品中价值最大的！为什么会输出第五次结果啊，应该输出4次才是对的！

°﹍M、Sulayman

wei_Y 发表于 2016-10-24 21:18
无解。

必    输出第五次！？~

wei_Y

°﹍M、Sulayman 发表于 2016-10-24 21:19
必    输出第五次！？~

说着玩的，见谅。

感觉建表时用字典好些？

somethings = {'A': [weight. price]}

使用列表然后index这种方法对有重复的数据时会出现很大的不准确性。

wei_Y

°﹍M、Sulayman 发表于 2016-10-24 21:19
必    输出第五次！？~

逻辑有些问题吧:

拿了东西 -> 判断重量 -> 是否放入背包。

现在的逻辑是: 判断重量 -> 拿东西放入背包 -> 判断重量 -> 拿东西放入背包。

°﹍M、Sulayman

wei_Y 发表于 2016-10-24 21:22
说着玩的，见谅。

感觉建表时用字典好些？

哇！对对对，受教了，原来是index捣的鬼啊，谢谢！！！！

wei_Y

°﹍M、Sulayman 发表于 2016-10-24 21:25
哇！对对对，受教了，原来是index捣的鬼啊，谢谢！！！！

不不不，index只是有时会出现失误。

°﹍M、Sulayman

wei_Y 发表于 2016-10-24 21:24
逻辑有些问题吧:

拿了东西 -> 判断重量 -> 是否放入背包。

我找对论坛了，万分感谢！我有时候写程序有点想当然！对对对，主要还是这个问题，我再看看！

°﹍M、Sulayman

wei_Y 发表于 2016-10-24 21:26
不不不，index只是有时会出现失误。

一个东西，我学了很多！再次感谢！刚学不久，把字典方法也忘记了，看来要用用~

wei_Y

°﹍M、Sulayman 发表于 2016-10-24 21:29
一个东西，我学了很多！再次感谢！刚学不久，把字典方法也忘记了，看来要用用~

共同进步。

之前也研究过贪心算法，可以看看哦~。
http://bbs.fishc.com/thread-56473-1-1.html

°﹍M、Sulayman

wei_Y 发表于 2016-10-24 21:31
共同进步。

之前也研究过贪心算法，可以看看哦~。

咳咳~我想说......老师留给我们的作业就是五大算法选其一你给我了链接......你你你要负责，万一我自己编不了。复制粘贴你的......我心里过意不去

wei_Y

°﹍M、Sulayman 发表于 2016-10-24 21:37
咳咳~我想说......老师留给我们的作业就是五大算法选其一你给我了链接......你你你要负责，万一 ...

等你复制粘贴了你会发现我的代码都是错的。啊哈哈哈。
话说哪五大呢。

°﹍M、Sulayman

wei_Y 发表于 2016-10-24 21:39
等你复制粘贴了你会发现我的代码都是错的。啊哈哈哈。
话说哪五大呢。

分治，动态规划，贪心，回溯，分支限界

jsjyyjs

贪心算法

jerryxjr1220

我写了个穷举法，对于你这种组合数量少的，还是很快的。
Max price 170,  Optimization:  (35, 30, 50, 10, 25)
[Finished in 0.2s]

1. bag = {35:10,30:40,60:30,50:50,40:35,10:40,25:30}
   
2. weight = [35,30,60,50,40,10,25]
   
3. 
   
4. import itertools as it
   
5. possible = []
   
6. for i in range(3,6):
   
7.         com = it.combinations(weight,i)
   
8.         for eachcom in com:
   
9.                 bagweight = 0
   
10.                 for eachitem in eachcom:
    
11.                         bagweight += eachitem
    
12.                 if bagweight <= 150:
    
13.                         possible.append(eachcom)
    
14. prices = []
    
15. for each in possible:
    
16.         bagprice = 0
    
17.         for e in each:
    
18.                 bagprice += bag[e]
    
19.         prices.append(bagprice)
    
20. maxprice = max(prices)
    
21. maxcom = possible[prices.index(maxprice)]
    
22. print ("Max price %d, " % maxprice, "Optimization: ", maxcom)

复制代码

°﹍M、Sulayman

jerryxjr1220 发表于 2016-10-24 22:44
我写了个穷举法，对于你这种组合数量少的，还是很快的。
Max price 170,  Optimization:  (35, 30, 50, 10 ...

谢谢！问题解决了已经，我发了个新帖。