python - 试图用python构造一个贪心算法

Question

所以我正在尝试为背包问题创建一个贪心算法。下面的txt文件就是knap20.txt文件。第一行给出了物品的数量，在本例中为 20。最后一行给出了背包的容量，在本例中为 524。其余行给出了每个项目的索引、价值和重量。

我的功能是理想地返回列表中的解决方案和权重值

从我的结果可以看出，我的程序运行正常。它是否像您期望的那样工作，我该如何改进它？

txt 文件

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

蟒蛇文件

import os
import matplotlib.pyplot as plt

def get_optimal_value(capacity, weights, values):
    value = 0.
    numItems = len(values)
    valuePerWeight = sorted([[values[i] / weights[i], weights[i]] for i in range(numItems)], reverse=True)
    while capacity > 0 and numItems > 0:
        maxi = 0
        idx = None
        for i in range(numItems):
            if valuePerWeight[i][1] > 0 and maxi < valuePerWeight[i][0]:
                maxi = valuePerWeight[i][0]
                idx = i

        if idx is None:
            return 0.
        if valuePerWeight[idx][1] <= capacity:
            value += valuePerWeight[idx][0]*valuePerWeight[idx][1]
            capacity -= valuePerWeight[idx][1]
        else:
            if valuePerWeight[idx][1] > 0:
                value += (capacity / valuePerWeight[idx][1]) * valuePerWeight[idx][1] * valuePerWeight[idx][0]
                return values, value
        valuePerWeight.pop(idx)
        numItems -= 1
    return value


def read_kfile(fname):
    print('file started')
    with open(fname) as kfile:
        print('fname found', fname)
        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, capacity, values, weights = read_kfile(knapfile)
val1,val2 = get_optimal_value(capacity, weights, values)
print ('values',val1)
print('value',val2)

结果

values [91, 60, 61, 9, 79, 46, 19, 57, 8, 84, 20, 72, 32, 31, 28, 81, 55, 43, 100, 27]
value 733.2394366197183

标签： python