algorithm - 计算组合

Question

我很难为下面给出的问题提出解决方案:

我们有 n 个盒子，每个盒子都有一个重量(这意味着盒子 B_i 中的每个球的重量为 C_i)，

每个盒子里都有一些球{b1,b2,b3...,b_n}(b_i 是 Box B_i 中球的数量)。

我们必须从中选择 m 个球，使得 m 个所选球的权重之和小于给定的数字 T。

有多少种方法可以做到？

Answer 1

首先，我们来看一个类似的问题:

类似的问题是:您希望最大化总和(使其仍然小于 T)，您面临着 subset-sum problem 的变体，即 NP-Hard .此线程中讨论了具有恒定数量项目的变化:Sum-subset with a fixed subset size .

另一种看待问题的方法是使用二维 knapsack problem ，其中权重 = 成本，以及元素数量的额外维度。此线程中讨论了此概念:What's the fastest way to solve knapsack prob with two properties

现在，看看您的问题:找到实现小于/等于 T 的总和的可能方法的数量仍然是 NP-Hard。

假设您有一个多项式算法来执行此操作，让它成为A。

运行 A(T) 和 A(T-1) 会给你两个数字，如果 A(T) > A(T-1) ，子集求和问题的答案应该是 true - 否则就是 false，所以给定这个问题的多项式解，我们可以证明 P= NP.