如何优化符合标准和规模目标的元素的选择？

Question

早上好,

想象一下许多袋子的清单(100)。每个袋子可以是颜色=红色/黄色/绿色，大小=小/大，重=是/否，羊毛=是/否。

我想选择符合以下条件的P=10包号：

• A=3红包数
• B=5小包数
• C=2数heavy=yes袋
• D=3数woolmade=yes袋

下面是一个具体的例子(简化为2个属性)：

• 10袋(id、色、毛制Y/N)清单：
  • (1 )红色，Y)，(2，红色，Y)，(3，红色，Y)，(4，红色，Y)，(5，红色，N)，(6，绿色，N)，(7，绿色，N)，(8，绿色，N)，(9，绿色，N)，(10，绿色，Y)

​

• 我想要5袋，3袋红色和4袋woolmade=Y
• 一个可能的答案是ID: 1、2、3、9和10。
• 下面的答案是不正确的：is 1，2，3，5和10，因为我将有4个红色(我只想要3个红色)和4个woolmade=Y (正确)

我对算法解释和可能的实现感兴趣(节点、java、python、vba、.)

谢谢

Answer 1

布鲁特力：

我只是在想，如何在所有可能的组合中寻找合适的组合。

有24种不同的袋子，所以有24 ^ 10种可能的组合。这些可以像数字一样生成到根24，只需增加这些数字。每个数字都可以根据您的标准进行检查。如果一个组合的检查需要1微秒，则需要大约17612小时来检查所有组合。只使用一个线程，在大约2年内，您可能会找到符合您的标准的所有可能的组合。

回溯：

如果您停留在第一个组合的10个袋子的工作，您实现了一个回溯算法。这可能会持续多久，我现在无法计算。

更好的布鲁特力量：

看看下面的例子，你会发现，并不是所有的基数24都是有趣的。这个问题可以通过查看0到23之间的10个数字元素的所有组合来解决，这些元素可能重复并检查这些元素。有92561040种可能的组合。这些检查可能会持续大约92秒。之后，您将有所有可能的组合来解决您的问题，如果您停止在第一个组合，您可能会更快。

示例

要理解这10个数字，请参见下面的袋子映射。

0000000000 10红色，10小，10重，10羊毛

0000000001 9红色，1黄色，10小，10重，10羊毛

0000000002 9红色，1绿色，10小，10重，10羊毛

..。

00000000A9红，1黄色，9小，1大，9重，1小，10毛

00000000B9红色，1绿色，9小，1大，9重，1小，10羊毛

..。

正如您所看到的，对于结果来说，只需要相同数字的名称，而不是位置。因此，有趣的组合数并不是基数24有10个位置的所有数字，而是所有在0到23之间的10个数字的组合，这些组合可以重复：(24 +10-1)！/((24-1)！10！)= 92561040个组合，如果每次检查需要1微秒，可以在92秒内检查。

制图：

• 红色/小型/是/是=0
• 黄色/小型/是/是=1
• 绿色/小型/是/是=2
• 红色/大/是/是=3
• 黄色/大/是/是=4
• 绿色/大/是/是=5
• 红色/小型/否/是=6
• 黄色/小型/否/是=7
• 绿色/小型/无/是=8
• 红色/大/否/是=9
• 黄色/大/否/是=A
• 绿色/大/不/是=B
• 红色/小型/是/否=C
• 黄色/小型/是/否=D
• 绿色/小型/是/否=E
• 红色/大/是/否=F
• 黄色/大/是/否=G
• 绿色/大/是/不=H
• 红色/小型/不/不=i
• 黄色/小型/不/不=J
• 绿色/小型/不/不=K
• 红/大/不/不=升
• 黄色/大/不/不=M
• 绿色/大/不/不=N