algorithm - 计算组合

Question

我在为以下问题提出解决方案时遇到困难：

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

每个盒子都包含一些球，特别是 {b1,b2,b3...,b_n}（b_i 是盒子 B_i 中的球数）。

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

有多少种方法可以做到？

Answer 1

首先，让我们看一个类似的问题：

类似的问题是：您正在寻求使总和最大化（使其仍然小于 T），您正面临子集和问题的变体，即NP-Hard。此线程中讨论了具有固定数量项目的变化：Sum-subset with a fixed subset size。

看待问题的另一种方法是使用二维背包问题，其中重量 = 成本，以及元素数量的额外维度。这个概念在这个线程中讨论：What's the faster 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。

Answer 2

您可以使用动态编程技术来解决它。

让表示从到f[i][j][k]选择j球的方法的数量，其权重总和为。你想得到的答案是。B_1B_i kf[n][m][T]

Initially, let f[i][j][k] = 1 for all i,j,k
for i = 1 to n
  for j = 0 to m
    for k = 0 to T
      for x = 0 to min(b_i,j)  # choose x balls from B_i
        y = x * C_i
        if y <= k
          f[i][j][k] = f[i][j][k] * f[i-1][j-x][k-y] * Comb(b_i,x)

Comb(n,k)是从元素中选择k元素的方式数n。

时间复杂度为 O(nm T b)，其中 b 是盒子中的最大球数。

请注意，由于T大 O 表示法中的 ，理论上它是 NP 难的。但是，在实际应用中，当T比较小时，这种算法还是可行的。