算法最优填充

Question

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

我想知道如何获得最佳的对象混合（或none混合），使得占据space的对象的值具有最高的潜在值。

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

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

我们有一个有限的 Space，大小为 10。

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

我想要一个 method/function 接受一个对象数组和一个大小以及 returns 一个具有最高潜在值的对象数组。

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

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 中呈线性（表示大小呈指数级）。当我们贪婪地 select 下一个要尝试的值时，首先尝试大值可能是好的，但实际上不是（参见示例）。

Answer 2

n : 0 1 2 3
space: 2 2 4 5
值：3 7 2 9
s = 10

那么通过包含总权重为 9 的项目 0,1 和 3，您可以获得的最大收益是 19。

 /* *   
 s = given limited space  
 n = current element  
 val = value array for each element  
 space = space occupied by each element  
 * */


 public int findMaximumBenefit(int s, int n, int [] val, int [] space)
{
    if (s == 0 || n == weight.length)
    {
        return 0;
    }

    // if this item's size is greater than space available
    // then this item cannot be included in the knapsack
    if (space[n] > s)
        return findMaximumBenefit(s, n+1, val, space);

    // Case1: maximum benefit possible by including current item in the knapsack
    int includeCaseBenefit = val[n] + findMaximumBenefit(s-space[n], n+1, val, space);

    // Case2: maximum benefit possible by excluding current item from the knapsack
    int excludeCaseBenefit = findMaximumBenefit(s, n+1, val, space);

    // return maximum of case1 and case2 values 
    return max(includeCaseBenefit, excludeCaseBenefit);
}

此功能在给定 space 限制的情况下为您提供最大可能的收益。现在，如果您还想知道哪些所有项目已被贡献以找到最大收益，那么您可以使用下面的 link http://www.ideserve.co.in/learn/dynamic-programming-0-1-knapsack-problem

算法最优填充

Algorithm optimal fill

algorithm

math

knapsack-problem