算法最优填充

Question

澄清我们有一个对象列表。每个对象都有一个属性 Size 和一个属性 Value。然后我们有一个有限的空间。

我想知道如何获得最佳的对象混合(或无混合)，以便占据空间的对象的值具有最高的潜在值。

所以大小和值(value)一样重要。每个对象的大小和值都是固定的，所以我不能有一半的对象。

例子所以我们有大小为 2、值为 5 的对象 A大小为 3，值为 8 的对象 B

我们的空间有限，大小为 10。

将对象放在空间中，我们可以看到我们可以有两个对象 A 实例和两个对象 B 实例，因此总值为 26。

我想要一个方法/函数，它接受一个对象数组和一个大小，并返回一个具有最高潜在值的对象数组。

很抱歉一开始没有把问题说清楚，反馈很好。希望上面更新的问题能澄清我想做什么。

Answer 1

我看到的第一点是解决方案不依赖于值的数量。仅考虑值就足够了。

给定一组值(例如{5、8、10、15})和所需的目标值，您可以使用动态规划:

def solve(values, target):
    # Try big values first to get smaller results.
    # Does not work in all cases.
    # values.sort(reverse=True)

    # Init an array with 0, -1, -1, ...
    added_to_reach = [None] * (target + 1)
    added_to_reach[0] = 0

    # Dynamically calculate if it is possible to
    # reach each value i up to target and store the
    # last added value in added_to_reach[i].
    for i in range(1, target + 1):
        for v in values:
            if i - v >= 0 and added_to_reach[i-v] is not None:
                added_to_reach[i] = v

    # Calculate the solution by going back.
    while added_to_reach[target] is None:
        target -= 1

    result = []
    while target > 0:
        result.append(added_to_reach[target])
        target -= added_to_reach[target]

    return result

print(solve([5, 10, 13, 14], 39))

在最坏的情况下，target 的复杂度是线性的(表示大小呈指数级)。当我们贪婪地选择下一个要尝试的值时，最好先尝试大值，但实际上并非如此(参见示例)。