python - 遍历表以找到最佳解决方案

Question

主题是背包问题。

我必须编写一个函数来返回最佳项目，即选择的项目。作为输入，它接收我的第一个函数返回的表和项目列表。

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)

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

Answer 1

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

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

以下是它在给定情况下的工作方式:

• 单元格 [5, 8](又名 [-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]