performance - 是否有一种算法可以在成本和大小限制下获得最高值(value)？

Question

我有一堆卡片。每张卡都有成本和值(value)。值越高，卡片越好。

我想用该系列中的最多 9 张牌组成一手牌。我必须将手牌的总成本保持在 70 以下。我如何做出总值(value)最高的手牌？

数字 9 和 70 是任意的，但适用于此样本集合(值(value)，成本)

collection = [
    [390,13],
    [294,7],
    [393,7],
    [448,7],
    [235,9],
    [389,9],
    [306,7],
    [263,8],
    [231,9],
    [256,7],
    [396,9],
    [379,9],
    [306,10],
    [240,9],
    [259,4],
    [160,4],
    [225,4],
    [190,3],
    [141,3],
    [188,3],
    [190,4],
    [192,4],
    [192,3],
    [282,5],
    [192,4],
    [169,3],
    [253,4],
    [219,4],
    [240,5]
]

背包方面

最大化 Sum(V[i]x[i]) i 从 1 到 n

服从 Sum(W[i]x[i]) <= 70 i 从 1 到 n

和 Sum(x[i]) <= 9 i 从 1 到 n

其中 x[i] 是 0 或 1

V是每张牌的值(value)

W是每张卡片的重量

Answer 1

这是我的背包问题版本，添加了元素数量限制(用 Python 编写)。 https://github.com/slek120/AutoDeck

在正常的背包问题中，您可以创建总成本最高的集合，从零开始递增，直到达到最大成本。下一组是前一组或总成本的集合中较好的一组 - 附加项目的项目成本。由于存在项目限制，因此必须更换项目，而不是仅附加项目。因此，使用总成本 - 项目成本 + 替换项目成本的集合。

我还创建了一个贪婪算法，它运行得更快但不能给出最佳答案。在这种情况下，您可以用最具成本效益的元素填充背包，直到达到元素限制。然后用下一个最具成本效益的项目替换该项目，该项目提供最多奖励。继续直到达到最大成本。