给定一个包含价格和价值的大列表，选择平均值大于或等于固定值的 10 个项目的最便宜组合
Given a big list of items with a price and a value, choose the cheapest combination of 10 items with an average value greater or equal to a fixed val
我不是计算机科学专业的，所以我对算法的了解相当有限。最近我在考虑某种市场机器人，但我有一个关键问题，我无法用蛮力解决。
Question: Let there be a list of items, where number of items are greater
than 10000. Each item has a value in between 0 and 1, and a price. Value and
price are independent of each other. You must choose the cheapest 10 items
where their average (or total) value is greater or equal than a given value.
我想到了几个算法如：
-Sort the list by price
-Divide the list in 5 item chunks, reducing the brute
force steps from 10000nCr10 to 2000nCr2.
显然它不会给出真正最便宜的组合，但希望足够接近？感谢您的帮助。
您可以使用整数线性规划求解。令物品 i 的价值为 v[i]，其成本为 c[i]。设 x[i] 是您购买的每件商品的数量（可以取值 0 或 1），V 是可接受的最小总价值。 x[i] 上的 0/1 约束使它成为整数线性程序而不是更简单的线性程序。
那么你想要最小化 sum(c[i]*x[i]) 使得 sum(v[i]*x[i]) >= V 和 sum(x[i]) = 10,这是作为ILP解决的正确形式的问题。
这是一个很好的 open-source 求解器：https://www.gnu.org/software/glpk/
我不是计算机科学专业的，所以我对算法的了解相当有限。最近我在考虑某种市场机器人，但我有一个关键问题，我无法用蛮力解决。
Question: Let there be a list of items, where number of items are greater
than 10000. Each item has a value in between 0 and 1, and a price. Value and
price are independent of each other. You must choose the cheapest 10 items
where their average (or total) value is greater or equal than a given value.
我想到了几个算法如：
-Sort the list by price
-Divide the list in 5 item chunks, reducing the brute
force steps from 10000nCr10 to 2000nCr2.
显然它不会给出真正最便宜的组合，但希望足够接近？感谢您的帮助。
您可以使用整数线性规划求解。令物品 i 的价值为 v[i]，其成本为 c[i]。设 x[i] 是您购买的每件商品的数量（可以取值 0 或 1），V 是可接受的最小总价值。 x[i] 上的 0/1 约束使它成为整数线性程序而不是更简单的线性程序。
那么你想要最小化 sum(c[i]*x[i]) 使得 sum(v[i]*x[i]) >= V 和 sum(x[i]) = 10,这是作为ILP解决的正确形式的问题。
这是一个很好的 open-source 求解器：https://www.gnu.org/software/glpk/