r语言 - 基于另一列总预算的15项的最高总价值

Question

我有一个3列(名称，值，成本)的数据集。我试图找到一种方法来从数据集返回15名,提供最高的价值成本总计200美元或更少。

理想情况下，我希望返回15个名称组合中提供最高组合值的前20个唯一条目。

示例数据集:

<表类> 名称 价值成本tbody><<tr>史蒂夫15美元7美元瑞秋20美元9美元亚当25美元6美元

你所描述的就是所谓的背包问题。除了一些特殊情况，这个问题已知是np完全的(维基百科)。这意味着没有"快速"的算法可以保证给你最大的解值。

在这种情况下，快速可以被认为"比尝试所有可能的组合并保留最佳组合要好得多"。对于一个小数据集和一台功能强大的计算机来说，这可能是实用的，但对于一个有100个名字的数据集来说，可能需要一周多的时间。

由于您已经指定了dplyr标签，您可能做的最好的事情就是选择那些具有最佳价值:成本比的项目。可能像下面这样:

output = dataset  %>%
mutate(ratio = value / cost) %>%
arrange(-ratio) %>% # sort descending
head(15) %>% # limit to at most 15 names
mutate(cumulative = cumsum(cost)) %>% # cost of names from best ratio to worst
filter(cumulative <= 200) %>% # discard least cost effective names to keep total cost under $200
select(names)