在给定 R 中的某些约束条件下计算最佳行集

Question

抱歉，标题听起来含糊不清，但这是设置：

我有一个零件清单，每个零件都有制造商、成本和利润。我将添加一个片段，但这将是一个很长的列表（数十个制造商，数百个零件）。

Manufacturer    Part Name   Cost    Profit
Cohiba          Behike 54   10.95   5.05
Rocky Patel     Edge        13.99   8.01
Acid            Liquid      8.49    3.51

我有一个代码可以对每个唯一的制造商随机抽取 select 个零件，然后计算成本和利润的总和。

ind <- sapply (unique( data$Manufacturer ) , function(x)
  sample( which(data$Manufacturer==x) , 1 ) )

Sampler <- data[ ind, ]

sum(Sampler$Profit)

sum(SamplerX$Cost)

我觉得必须有一种更聪明的方法来要求它简单地找到每个制造商的一个独特零件的最佳列表，从而以最低的成本给我最高的利润。谁能给我一些见识？

Answer 1

我必须完全感谢 PavoDive 帮助我解决了这个问题。他对短语 "Knapsack Problem" 的使用让我头晕目眩，因为自从中学以来我就没有听过背包谜语的版本。

一旦他这么说，我就能够快速连接点并且实际上发现已经存在一个包来解决这个确切设置的背包问题：

http://www.inside-r.org/packages/cran/adagio/docs/knapsack

我需要的答案就在那里。分享这个以防其他人需要解决这个问题。

Answer 2

完整性：

背包问题是强盗想要最大化被盗物品的价格，同时将重量保持在或低于他的背包容量的问题。 adagio包有功能可以解决。

library(adagio)
# create some random data:
set.seed(1)
weights <- sample(1:100,30,FALSE)
prices <- sample(1:10000,30,FALSE)

# find what is the total weight
sum(weights)
[1] 1383

# Solve the problem, allowing a capacity of about 10% the total weight:
a <- knapsack(w=weights, p=prices, cap=138)

# See what a returns:
a
$capacity
[1] 138

$profit
[1] 50928

$indices
[1]  1  5 10 11 12 19 22 27

# validate results:
sum(weights[a$indices])
[1] 138

请记住，如果您的向量很大，则需要很大的容量。

####### 编辑以添加 #######

考虑到您想在将成本保持在一定限度以下的同时实现利润最大化，AND 不超过一定数量的制造商（在您的问题中是一个），这是两个-dimensional knapsack 问题，我没有找到任何解决它的函数或包。

备选方案：

自己编写代码：一个好的开始是 adagio::knapsack（没有括号，所以您可以看到代码），然后谷歌搜索 "two dimensional knapsack"。伪代码中有很多算法，因此您不会从空白开始 sheet.
解决方法：如果您的输出向量不是很大，您可以使用 adagio::knapsack() 忽略制造商 并找到一个接近的解决方案。然后你必须手动查找结果向量中重复的制造商，然后找到一个尽可能接近低于要替换的项目成本并且属于的项目一个不同的，尚未使用的制造商，具有最高的利润。 请注意这不一定会产生最佳可用解决方案，即最优解（问题是 NP-hard，所以无论如何它可能不会），但它会是一个很好的近似值。

在给定 R 中的某些约束条件下计算最佳行集

Calculating an optimum set of rows given certain constraints in R

r

knapsack-problem

mathematical-optimization