两个背包的值之和具有最小的 delta

Question

这个问题是我在工作中实现某个系统时遇到的改写问题。我认为这有点类似于背包问题，并且很好奇地探索如何解决它，因为我无法提出解决方案。

问题陈述：给定一组物品，每个物品都有重量和价值，还有两个背包，确定哪些物品要包含在这两个背包中，这样每个背包的重量正好是 K 和价值总和的增量这两个背包越小越好。如果不可能满足两个背包算法的重量约束应该 return 没有。

我认为某种贪心算法可能是一个令人满意的解决方案，但不确定如何编写它。

Answer 1

这可以用动态规划的方法来解决。这是一种使用链表的方法。

from collections import namedtuple

ListEntry = namedtuple('ListEntry', 'id weight value prev')
Thing = namedtuple('Thing', 'weight value')

def add_entry_to_list(i, e, l):
    return ListEntry(i, l.weight + e.weight, l.value + e.value, l)

def split_entries (entries, target_weight):
    empty_list = ListEntry(None, 0, 0, None)
    dp_soln = { (0, 0): (empty_list, empty_list) }

    for i in range(len(entries)):
        dp_soln_new = {}
        e = entries[i]
        for k, v in dp_soln.items():
            (weight_l, weight_r) = k
            (l_left, l_right) = v

            this_options = {k: v}
            this_options[(weight_l + e.weight, weight_r)] = (add_entry_to_list(i, e, l_left), l_right)
            this_options[(weight_l, weight_r + e.weight)] = (l_left, add_entry_to_list(i, e, l_right))

            for o_k, o_v in this_options.items():
                if target_weight < max(o_k):
                    pass # Can't lead to (target_weight, target_weight)
                elif o_k not in dp_soln_new:
                    dp_soln_new[o_k] = o_v
                else:
                    diff = o_v[0].value - o_v[1].value
                    existing_diff = dp_soln_new[o_k][0].value - dp_soln_new[o_k][1].value
                    if existing_diff < diff:
                        dp_soln_new[o_k] = o_v
        dp_soln = dp_soln_new

    final_key = (target_weight, target_weight)
    if final_key in dp_soln:
        return dp_soln[final_key]
    else:
        return None

print(split_entries([
    Thing(1, 3),
    Thing(1, 4),
    Thing(2, 1),
    Thing(2, 5),
    ], 3))

两个背包的值之和具有最小的 delta

Two knapsacks with smallest delta in sum of values

algorithm

knapsack-problem