python - 使用贪心python算法解决背包问题
问题描述
我正在尝试使用 Python 解决背包问题,实现贪心算法。我回来的结果对我来说毫无意义。
背包:
第一行给出了物品的数量,在本例中为 20。最后一行给出了背包的容量,在本例中为 524。其余行给出了每个项目的索引、价值和重量。
20
1 91 29
2 60 65
3 61 71
4 9 60
5 79 45
6 46 71
7 19 22
8 57 97
9 8 6
10 84 91
11 20 57
12 72 60
13 32 49
14 31 89
15 28 2
16 81 30
17 55 90
18 43 25
19 100 82
20 27 19
524
Python代码:
import os
def constructive():
knapsack = []
Weight = 0
while(Weight <= cap):
best = max(values)
i = values.index(best)
knapsack.append(i)
Weight = Weight + weights[i]
del values[i]
del weights[i]
return knapsack, Weight
def read_kfile(fname):
with open(fname, 'rU') as kfile:
lines = kfile.readlines() # reads the whole file
n = int(lines[0])
c = int(lines[n+1])
vs = []
ws = []
lines = lines[1:n+1] # Removes the first and last line
for l in lines:
numbers = l.split() # Converts the string into a list
vs.append(int(numbers[1])) # Appends value, need to convert to int
ws.append(int(numbers[2])) # Appends weigth, need to convert to int
return n, c, vs, ws
dir_path = os.path.dirname(os.path.realpath(__file__)) # Get the directory where the file is located
os.chdir(dir_path) # Change the working directory so we can read the file
knapfile = 'knap20.txt'
nitems, cap, values, weights = read_kfile(knapfile)
val1,val2 =constructive()
print ('knapsack',val1)
print('weight', val2)
print('cap', cap)
结果:
knapsack [18, 0, 8, 13, 3, 8, 1, 0, 3]
weight 570
cap 524
解决方案
欢迎。您的程序给出的权重超过上限的原因是因为在您放入背包的最后一件物品上,您没有检查它是否可以放入其中。为此,只需添加一个 if 语句,您还应该检查值列表是否为空。请注意,我已附加 (i+1),因为您的文本文件的索引从 1 开始,但 Python 从 0 开始它的列表索引:
def constructive():
knapsack = []
Weight = 0
while(Weight <= cap and values):
best = max(values)
i = values.index(best)
if weights[i] <= cap-Weight:
knapsack.append(i+1)
Weight = Weight + weights[i]
del values[i]
del weights[i]
return knapsack, Weight
推荐阅读
- apache-flink - 无法在 flink 中读取带前缀的 s3 文件
- excel - 使用文本框过滤列表框脚本问题
- firebase - Firebase实时数据库检查有两个值?
- python-3.x - Python 3 Zeep 登录和 cookie 问题?
- sql - 不使用 GO 重复插入语句
- android - MotionLayout 阻止所有视图上的 ClickListener
- python-3.x - Windows10Pro-64 不支持 win_amd64.whl
- c# - C# 编码问题,字符 '¤' 结果为 '?'
- swift - Can you disable App-opening mechanism when the user presses the Notification Banner?
- python - I have a coding question which i have solved in python3. But i would like to know if there is better way of writing this to run faster in python3