遍历 a Table 求最优解

Question

题目是背包问题。

我必须写一个函数，returns 最好的项目，意思是选择的项目。作为输入，它接收 table 我返回的第一个函数和项目列表。

def make_table(items, max_wt):
    table = [[(0, 0) for x in range(max_wt+ 1)] for y in range(len(items) + 1)]
    for i in range(1, len(items) + 1):
        for j in range(1, max_wt + 1):  # lines: lists every item
            (vl, wt) = items[i - 1]  # rows: lists every weight
            # if weight of the current item exceeds current max possible weight, take the value from the above cell
            if wt > j: 
                table[i][j] = (table[i - 1][j][0], 0)
            # if not, compare the last optimal solution with the new (potentially) best solution
            else:
                last_opt = table[i - 1][j][0]
                new_opt = table[i - 1][j - wt][0] + vl
                if last_opt >= new_opt:  # Choose whichever has the highest value
                    table[i][j] = (last_opt, 0) # flag 1 if used to preserve the max value, 0 if not
                else:
                    table[i][j] = (new_opt, 1)
    return table

def run_table(table, items):
item_ct = len(items)
manifest = [0] * item_ct
# Start at end of table and retrace steps back to an empty pack.
# The table is organized by item (rows) and weight (columns).

soln_wt = maximum_wt    # Weight of the remaining solution 
for item_no in range(item_ct, 0, -1):
    print("Check item", item_no, "\t weight", soln_wt)
    wt, used = table[item_no][soln_wt]

    if used:
        manifest[item_no-1] = 1
        soln_wt -= items[item_no-1][1]

return manifest

val_wt = [(3,4),(1,1),(4,5),(3,4),(2,2)]
maximum_wt = 8
T = createTable(val_wt, maximum_wt)

best_vl = T[-1][-1][0]  # should be the maximum value ( = 7 )
print("Best packing", best_vl)
L = run_table(T, val_wt)  # should return [0, 1, 1, 0, 1]
print(L)

如何遍历这个table来恢复包含在最优解中的项？

Answer 1

从 table 的右下角开始，您需要回溯创建逻辑。一般规则是：

如果当前单元格被标记为1，则将当前项添加到解决方案集中，并向左移动weight个单元格。
否则当前项在解集中不
上移一排

以下是它在给定案例中的工作原理：

单元格 [5, 8] (a.k.a. [-1, -1]) 被标记为 1；将项目 5 添加到解决方案集（现在为 [0, 0, 0, 0, 1]）并向左移动权重 items[5,1]，即 2。同时向上移动一行到 [4, 6]
单元格 [4, 6] 被标记为 0；第 4 项不在解决方案中。向上移动一排。
单元格 [3, 6] 被标记为 1；将项目 3 添加到解决方案中（现在为 [0, 0, 1, 0, 1]）并向左移动 5 的权重，然后向上移动一行。
单元格 [2, 1] 被标记为 1；将项目 2 添加到解决方案中（现在为 [0, 1, 1, 0, 1]）并向左移动 1 的权重，然后向上移动一行。
单元格 [1, 1] 被标记为 0；第 1 项不在解决方案中。向上移动一排。

没有更多项目要检查，我们就完成了。解是01101.

代码

def run_table(table, items):
    item_ct = len(items)
    manifest = [0] * item_ct
    # Start at end of table and retrace steps back to an empty pack.
    # The table is organized by item (rows) and weight (columns).

    soln_wt = maxWeight    # Weight of the remaining solution 
    for item_no in range(item_ct, 0, -1):
        print("Check item", item_no, "\t weight", soln_wt)
        wt, used = table[item_no][soln_wt]

        if used:
            manifest[item_no-1] = 1
            soln_wt -= items[item_no-1][1]

    return manifest

val_wt = [(3,4),(1,1),(4,5),(3,4),(2,2)]
maxWeight = 8
T = createTable(val_wt, maxWeight)

bestValue = T[-1][-1][0]  # should be the maximum value ( = 7 )
print("Best packing", bestValue)
L = run_table(T, val_wt)  # should return [0, 1, 1, 0, 1]
print(L)

输出：

Best packing 7
Check item 5     weight 8
Check item 4     weight 6
Check item 3     weight 6
Check item 2     weight 1
Check item 1     weight 0
[0, 1, 1, 0, 1]

遍历 a Table 求最优解

Traverse a Table to Find the Optimal Solution

python

algorithm

knapsack-problem

dynamic-programming