使用Python实现贪心算法
使用Python实现贪心算法
题目：
圣诞节来临了，在城市A中，圣诞老人准备分发糖果。现在有多箱不同的糖果，每一种糖果都有自己的价值和重量。每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果。请问圣诞老人最多能带走多大价值的糖果。
输入数据：
输入的第一行由两个部分组成，分别为糖果箱数正整数n(1<=n<=100)，驯鹿能承受的最大重量正整数w(0<w<10000)；其余n行每行对应一箱糖果，由两部分正整数v和w组成，分别为一箱糖果的价值和重量。
输出要求：
输出圣诞老人能带走的糖果的最大总价值，保留一位小数，输出为一行。
输出样例：
4 15
100 4
412 8
266 7
591 2
输出样例:
1193.0
注：此处并没有按照这样的格式进行输入。
1 #coding:utf-8 2 from __future__ import division 3 4 input_a = raw_input(u'箱数:') 5 input_b = raw_input(u'最大承受重量:') 6 7 list_c = [] 8 list_z = [] 9 10 for i in range(1,int(input_a)+1): 11 input_c = raw_input('第'+str(i)+'箱的总价值:') 12 input_d = raw_input('第'+str(i)+'箱的重量:') 13 avg = round(int(input_c)/int(input_d),1)#每一箱，重量为1的价值 14 list_c.append(avg)#添加到列表，用于之后做比较 15 list_z.append([int(input_d),avg,0])#此处列表中添加列表，中间的列表一个存放总重量，第二个存放单位价值，第三个存放是否该物品已被取走 16 17 list_c.sort(reverse=True) # 降序排序 18 sum =[0,0]# 用于存放取走的总重量，第一个参数是取走的重量，第二个是超出前的备份 19 num =0 20 ji = 0 21 22 23 for i in range(len(list_c)): 24 for k in range(len(list_z)): 25 if ji == 0:#做是否超出马车最大承受量的标记，未超出为0 26 if (list_c[i] == list_z[k][1]) and (list_z[k][2]==0): 27 sum[1] = sum[0]#备份 28 sum[0] = sum[0] + list_z[k][0]#取走的重量 29 v = list_z[k][0]#取走的重量 30 if sum[0] > int(input_b):#如果所有取走的重量超出马车的重量，就依次减少一单元的重量 31 ji = 1#超出为1 32 t= list_z[k][0] 33 while True:#依次减去单位1的重量 34 z = sum[1] + t#使用备份进行判断，此时取走的数量已经大于最大承受量了 35 if z <= int(input_b): 36 break 37 t = t-1 38 v=t#等于最大承受量时，价值较大的一件物品应取走的数量 39 sum[0]=sum[1]#从备份恢复 40 sum[0] = sum[0] + t#此时为真正的取走数量 41 num = list_c[i]*v + num#总价值 42 list_z[k][2] = 1#取走的标记 43 print u'能带走的糖果的最大价值为:',num
实现的效果图：
此处用两组数据进行测试：
第一组数据：
第二组数据:
如果各位大佬有更好的方法，欢迎以下评论区说下，如果有什么不懂得，也同样欢迎评论区发表疑问。谢谢！
版权声明：本文为zhy128原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。