0-1 背包，对超重和超重情况进行处罚
0-1 Knapsack with penalty for under and overweight cases
假设一个经典的 0-1 背包问题，但您可以 overflow/underflow 被罚下。每单位溢出（重量超过最大容量）扣除X利润，每单位下溢（重量低于最大容量）扣除Y利润。
我想按利润与重量的比率对所有物品进行排序，然后尝试像普通背包问题一样装满麻袋，然后对于剩余重量和物品，我通过考虑下溢和溢出来计算额外利润。
此解决方案在某些情况下会失败，例如当有 3 个项目的权重分别为 30、20、10 和利润分别为 30、25、20 时。允许的最大权重为 39，下溢惩罚为 5，溢出惩罚为 10。
我的解决方案是像普通背包一样解决它，然后考虑惩罚，所以它给出了选择重量为 20,10 的项目的解决方案，但它没有添加重量为 30 的项目，因为它的惩罚高于利润。最优解应该是选择权重30和10的项目。我现在唯一能想到的就是暴力破解，尽量避免。如果有人能想到任何其他解决方案，那就太好了！
您仍然可以使用标准动态规划。
让我们计算从0到数组所有元素之和的所有s是否可达总和s。这正是标准动态规划解决方案所做的。我们这里不关心惩罚。
让我们遍历所有可达的总和并选择最佳的总和，同时考虑到溢出（或不足）流量的惩罚。
您可以将其分解为两个子问题，一个具有权重不足的惩罚，一个具有超重的惩罚。更具体地说，您可以通过解决两个不同的 integer linear programming problems 并取两个解决方案中的最佳解决方案来解决问题：
假设您有 n 项权重 w1,w2,...,wn 和值 v1, v2, ..., vn。假设重量容量是 C，减重的惩罚是 A，超重的惩罚是 B（每单位）。
在这两个问题中，让二元决策变量为 x1, ..., xn，表示相应的项目是否 selected。
问题 1)
max v1*x1 + v2*x2 + ... + vn*xn - A*(C - w1*x1 - w2*x2 - ... - wn*xn)
subject to
w1*x1 + w2*x2 + ... + wn*xn <= C
请注意，通过代数，objective 函数与仿射表达式
相同
(v1 + A*w1)*x1 + ... + (vn + A*wn)*xn - A*C
并在相同值处最大化 x1, ..., xn 最大化纯线性函数
(v1 + A*w1)*x1 + ... + (vn + A*wn)*xn
这个子问题可以使用任何 ILP 求解器来求解，或者就像普通的背包问题一样求解。
问题 2)
max v1*x1 + v2*x2 + ... + vn*xn - B*(w1*x1 + w2*x2 + ... + wn*xn - C)
subject to
w1*x1 + w2*x2 + ... + wn*xn >= C
可以通过最大化线性objective函数来求解
(v1 - B*w1)*x1 + ... + (vn - B*wn)*xn
同样，这可以用任何 ILP 求解器来解决。这个问题不是背包问题，因为主要约束中的不等式指向了错误的方向，尽管可能有某种方法可以将其简化为背包问题。
编辑时。第二个问题也可以作为背包问题来解决——您可以在其中决定哪些物品不包括在内。从包含所有内容的解决方案开始。如果这不可行（如果所有权重的总和不超过容量）那么你就完成了。问题1的解是全局解。除此以外。定义 surplus, S, 为
S = w1 + w2 + ... + wn - C
现在，解决下面的背包问题：
weights: w1, w2, ..., wn //same as before
values: Bw1 - v1, Bw2 - v2, ..., BWn - vn
capacity: S
关于值的一句话：Bwi - vi 是衡量删除 第 i 个对象有多大帮助的方法（假设删除它会使您保持在原始容量之上这样你就不需要考虑体重过轻的处罚）。一方面，它消除了部分惩罚，Bwi，但另一方面，它又带走了一些价值，vi。
解决这个背包问题后 -- 移除这些物品。剩下的项目是问题2的解决方案。
让我们看看这对您的玩具问题有何影响：
weights: 30, 20, 10
values: 20, 25, 20
C: 39
A: 5 //per-unit underflow penalty
B: 10 //per-unit overflow penalty
对于问题1，解决如下背包问题：
weights: 30, 20, 10
values: 170, 125, 70 // = 20 + 5*30, 25 + 5*20, 20 + 5*10
C: 39
这有解决方案：包括 20、10，值为 195。就原始问题而言，它的值为 195 - 5*39 = 0。这似乎有点奇怪，但就原始问题而言，该值使用最后两项的结果是 25 + 20 = 45 但它会让你少了 9 个单位，惩罚是 5*9 = 45 和 45 - 45 = 0
第二个问题：
weights: 30, 20, 10
values: 280, 175, 80 // = 10*30 - 20, 10*20 - 25, 10*10 - 20
S: 26 // = 30 + 20 + 10 - 39
这道题的解法显然是select20。也就是说20是selected for non-inclusion。这意味着对于第二个问题，我想包括权重为 30 和 10 的对象。
这样做的价值是（就原问题而言）
20 + 20 - 10*1 = 30
由于30 > 0（解1的值），这是整体最优解。
总结一下：您可以通过解决两个普通的背包问题来找到两个候选解决方案，然后取两者中较好的一个来解决您的背包问题。如果您已经有了解决背包问题的函数，那么编写另一个调用它两次、解释输出和 returns 最佳解决方案的函数应该不会太难。
假设一个经典的 0-1 背包问题，但您可以 overflow/underflow 被罚下。每单位溢出（重量超过最大容量）扣除X利润，每单位下溢（重量低于最大容量）扣除Y利润。
我想按利润与重量的比率对所有物品进行排序，然后尝试像普通背包问题一样装满麻袋，然后对于剩余重量和物品，我通过考虑下溢和溢出来计算额外利润。
此解决方案在某些情况下会失败，例如当有 3 个项目的权重分别为 30、20、10 和利润分别为 30、25、20 时。允许的最大权重为 39，下溢惩罚为 5，溢出惩罚为 10。
我的解决方案是像普通背包一样解决它，然后考虑惩罚，所以它给出了选择重量为 20,10 的项目的解决方案，但它没有添加重量为 30 的项目，因为它的惩罚高于利润。最优解应该是选择权重30和10的项目。我现在唯一能想到的就是暴力破解，尽量避免。如果有人能想到任何其他解决方案，那就太好了！
您仍然可以使用标准动态规划。
让我们计算从
0到数组所有元素之和的所有s是否可达总和s。这正是标准动态规划解决方案所做的。我们这里不关心惩罚。让我们遍历所有可达的总和并选择最佳的总和，同时考虑到溢出（或不足）流量的惩罚。
您可以将其分解为两个子问题，一个具有权重不足的惩罚，一个具有超重的惩罚。更具体地说，您可以通过解决两个不同的 integer linear programming problems 并取两个解决方案中的最佳解决方案来解决问题：
假设您有 n 项权重 w1,w2,...,wn 和值 v1, v2, ..., vn。假设重量容量是 C，减重的惩罚是 A，超重的惩罚是 B（每单位）。
在这两个问题中，让二元决策变量为 x1, ..., xn，表示相应的项目是否 selected。
问题 1)
max v1*x1 + v2*x2 + ... + vn*xn - A*(C - w1*x1 - w2*x2 - ... - wn*xn)
subject to
w1*x1 + w2*x2 + ... + wn*xn <= C
请注意，通过代数，objective 函数与仿射表达式
相同(v1 + A*w1)*x1 + ... + (vn + A*wn)*xn - A*C
并在相同值处最大化 x1, ..., xn 最大化纯线性函数
(v1 + A*w1)*x1 + ... + (vn + A*wn)*xn
这个子问题可以使用任何 ILP 求解器来求解，或者就像普通的背包问题一样求解。
问题 2)
max v1*x1 + v2*x2 + ... + vn*xn - B*(w1*x1 + w2*x2 + ... + wn*xn - C)
subject to
w1*x1 + w2*x2 + ... + wn*xn >= C
可以通过最大化线性objective函数来求解
(v1 - B*w1)*x1 + ... + (vn - B*wn)*xn
同样，这可以用任何 ILP 求解器来解决。这个问题不是背包问题，因为主要约束中的不等式指向了错误的方向，尽管可能有某种方法可以将其简化为背包问题。
编辑时。第二个问题也可以作为背包问题来解决——您可以在其中决定哪些物品不包括在内。从包含所有内容的解决方案开始。如果这不可行（如果所有权重的总和不超过容量）那么你就完成了。问题1的解是全局解。除此以外。定义 surplus, S, 为
S = w1 + w2 + ... + wn - C
现在，解决下面的背包问题：
weights: w1, w2, ..., wn //same as before
values: Bw1 - v1, Bw2 - v2, ..., BWn - vn
capacity: S
关于值的一句话：Bwi - vi 是衡量删除 第 i 个对象有多大帮助的方法（假设删除它会使您保持在原始容量之上这样你就不需要考虑体重过轻的处罚）。一方面，它消除了部分惩罚，Bwi，但另一方面，它又带走了一些价值，vi。
解决这个背包问题后 -- 移除这些物品。剩下的项目是问题2的解决方案。
让我们看看这对您的玩具问题有何影响：
weights: 30, 20, 10
values: 20, 25, 20
C: 39
A: 5 //per-unit underflow penalty
B: 10 //per-unit overflow penalty
对于问题1，解决如下背包问题：
weights: 30, 20, 10
values: 170, 125, 70 // = 20 + 5*30, 25 + 5*20, 20 + 5*10
C: 39
这有解决方案：包括 20、10，值为 195。就原始问题而言，它的值为 195 - 5*39 = 0。这似乎有点奇怪，但就原始问题而言，该值使用最后两项的结果是 25 + 20 = 45 但它会让你少了 9 个单位，惩罚是 5*9 = 45 和 45 - 45 = 0
第二个问题：
weights: 30, 20, 10
values: 280, 175, 80 // = 10*30 - 20, 10*20 - 25, 10*10 - 20
S: 26 // = 30 + 20 + 10 - 39
这道题的解法显然是select20。也就是说20是selected for non-inclusion。这意味着对于第二个问题，我想包括权重为 30 和 10 的对象。
这样做的价值是（就原问题而言）
20 + 20 - 10*1 = 30
由于30 > 0（解1的值），这是整体最优解。
总结一下：您可以通过解决两个普通的背包问题来找到两个候选解决方案，然后取两者中较好的一个来解决您的背包问题。如果您已经有了解决背包问题的函数，那么编写另一个调用它两次、解释输出和 returns 最佳解决方案的函数应该不会太难。