数组所有可能的组合
All possible combination of an array
我正在尝试查找数组的所有可能组合。我找不到类似的问题所以我在这里问。
假设我有数组 A 和 N ，整数 T 作为输入，我需要找到满足以下不等式的数组 S 的所有可能组合。
输入：A(a1,a2,...,ak), N(n1,n2,...,nk), int T
输出：S(s1,s2,....sk)
受制于：
总和 ( si*ai ) <= T
和
对于每个 i: si<= ni
有什么想法吗？你如何实施它？我将使用 C++ 来实现它。
会有无解、无限多解、有限解的情况
首先定义SUM(X,Y) = x_1*y_1 + x_2*y_2 + ... + x_k*y_k.
if SUM(A,N) <= T then N 是一个解决方案。
接下来，让Ni = (n_1, n_2, ..., [n_i]-1, ..., n_k)。如果从 1 到 k 中的任意 i SUM(A,Ni) < SUM(A,N) 则有无穷多个解。我们无法枚举它们，我们完成了。
否则，如果N不是解决方案，那么就没有解决方案，我们就完成了。
最后，如果以上两种情况都不成立，则有有限多解。要枚举它们，再次从 i=1 迭代到 k 并保持所有其他 n 不变，继续将 n_i 递减 1 以获得 Ni' 并检查是否 SUM(A,Ni') <= T。跟踪每个 n 的这些范围，因为这些将是每个 n 可以独立于其他变化并且仍然（可能）给出解决方案的最大范围。
最后，遍历所有确定的 n 范围的笛卡尔积，并检查每个组合是否是一个解决方案。
我可能仍然遗漏了一些极端情况，但我认为这主要是一个正确的解决方案。
我正在尝试查找数组的所有可能组合。我找不到类似的问题所以我在这里问。
假设我有数组 A 和 N ，整数 T 作为输入，我需要找到满足以下不等式的数组 S 的所有可能组合。
输入：A(a1,a2,...,ak), N(n1,n2,...,nk), int T
输出：S(s1,s2,....sk)
受制于：
总和 ( si*ai ) <= T
和
对于每个 i: si<= ni
有什么想法吗？你如何实施它？我将使用 C++ 来实现它。
会有无解、无限多解、有限解的情况
首先定义SUM(X,Y) = x_1*y_1 + x_2*y_2 + ... + x_k*y_k.
if SUM(A,N) <= T then N 是一个解决方案。
接下来，让Ni = (n_1, n_2, ..., [n_i]-1, ..., n_k)。如果从 1 到 k 中的任意 i SUM(A,Ni) < SUM(A,N) 则有无穷多个解。我们无法枚举它们，我们完成了。
否则，如果N不是解决方案，那么就没有解决方案，我们就完成了。
最后，如果以上两种情况都不成立，则有有限多解。要枚举它们，再次从 i=1 迭代到 k 并保持所有其他 n 不变，继续将 n_i 递减 1 以获得 Ni' 并检查是否 SUM(A,Ni') <= T。跟踪每个 n 的这些范围，因为这些将是每个 n 可以独立于其他变化并且仍然（可能）给出解决方案的最大范围。
最后，遍历所有确定的 n 范围的笛卡尔积，并检查每个组合是否是一个解决方案。
我可能仍然遗漏了一些极端情况，但我认为这主要是一个正确的解决方案。