0

我有以下选择问题：给定 N 个项目的总体，每个项目具有 +ve 成本（C_i）并给定用户输入 k 和总成本 S。从 N 个项目的总体中找到最优的 k 个项目，使得 abs( S-sum(C_i)) 是最小值。

将不胜感激任何帮助

4

1 回答 1

0

您对 N 或 S 有限制吗？如果 N 很小，您可以尝试所有子集。如果 S 很小，您可以用背包解决它（查找 min sum(C_i)>=​​S 和 max sum(C_i)<=S）

于 2012-11-30T23:00:56.040 回答