使用贪心 python 算法解决背包问题
Solving knapsack problem using a greedy python algorithm
我正在尝试使用 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
问题是——在最后一步——你找到的最好的物品将超过最大重量。但是既然你已经进入了循环,你还是要添加它。
在下一次迭代中,您意识到自己超出了上限并停止。
我不确定一旦下一个最好的太重,你想如何进行。如果你只是想停止而不添加任何东西,你可以简单地修改你的 constructive
如下所示:
def constructive():
knapsack = []
Weight = 0
while(True):
best = max(values)
i = values.index(best)
if Weight + weights[i] > cap:
break
knapsack.append(i)
Weight = Weight + weights[i]
del values[i]
del weights[i]
return knapsack, Weight
我正在尝试使用 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
问题是——在最后一步——你找到的最好的物品将超过最大重量。但是既然你已经进入了循环,你还是要添加它。 在下一次迭代中,您意识到自己超出了上限并停止。
我不确定一旦下一个最好的太重,你想如何进行。如果你只是想停止而不添加任何东西,你可以简单地修改你的 constructive
如下所示:
def constructive():
knapsack = []
Weight = 0
while(True):
best = max(values)
i = values.index(best)
if Weight + weights[i] > cap:
break
knapsack.append(i)
Weight = Weight + weights[i]
del values[i]
del weights[i]
return knapsack, Weight