c# - 我需要满足条件的随机算法

Question

假设我在数据库中有一个 Product 表，它具有以下 id 和 price 属性:

Product
=======
ProductId int PRIMARY KEY
Price int

为简单起见，我将把 Price 作为 int 数据类型。所以现在我想使用一种随机算法，该算法将从数据库中检索 n 条记录，从而 Price 总和为固定数量 m.

例如:

• n = 5
• 米=100

所以我将检索 5 个 Product 记录，Price 加起来为 100。

一个可能的结果:

ProductId       Price
=====================
       5          10
     109          27
    2081          31
     139          21
     331          11
======================
           Sum:  100

我尝试过暴力破解方法，但似乎需要很长时间才能得到 100 的正确总和。有什么算法可以做到这一点吗？

Answer 1

您的问题可以看作是子集求和问题。您可以在这里找到与之相关的所有信息:

Wiki:Subset Problem

如果您需要精确值，问题是 NP(无法解决大量数据)，如果近似值没问题，您有一些选择。