背包的变种 [英] Variant of Knapsack

问题描述

我正在开发一个解决0/1背包问题变体的程序。

原始问题在这里描述： https://en.wikipedia.org/wiki/Knapsack_problem 。
以防万一将来链接丢失，我将为您简要介绍0/1背包问题（如果您对此很熟悉，请跳过此段）：
假设我们有 n 个项目，每个项目的权重 wi 且值 vi 。我们希望将物品放入一个最大重量为 W 的袋子中，以便袋子内的总价值是最大可能而不会增加袋子的重量。项目不能有多个实例（即，我们每个实例只有一个）。问题的目的是和 xi = 0，1 （ xi 表示物品在包中的状态）。

就我而言，条件和目标都有细微差别：

• 所有项目的权重为1， wi = 1，i = 1 ... n




• 我总是想把一半的东西放进袋子。因此，袋子的最大重量是物品数量的一半（向上舍入）。 W = ceil [n / 2] 或 W = floor [（n + 1）/ 2] 。




• 此外，袋子内的重量必须等于其最大重量容量 SUM（wi.xi）= W

最后，而不是最大化袋中物品的价值，目的是使里面物品的价值尽可能接近外面物品的价值。因此，我的目标是使最小化| SUM（vi.-xi）-SUM [vi（1-xi）] | ，简化为 minimize | SUM [vi（2xi-1）] | 。

现在，原始0/1有一个伪代码上面的Wikipedia页面上的背包问题（您可以在本文的底部找到它），但是我很难适应它的情况。有人可以帮忙吗？ （我不是要代码，只是想提供一个想法，所以语言是无关紧要的）。

谢谢！

---

维基百科针对0/1背包问题的伪代码：

假设 w1，w2，...，wn，W 严格是正整数。将
m [i，w] 定义为重量小于或等于的
可获得的最大值w 使用不超过 i 的商品（前 i 个商品）。

我们可以递归定义 m [i，w] 如下：

• m [0，w] = 0


• m [i， w] = m [i-1，w]，如果wi> w （新商品超出了当前的重量限制）


• m [i，w] = max（m [i- 1，w]，m [i-1，w-wi] + vi）如果wi< = w 。

然后可以通过计算 m [n，W] 来找到解决方案。

  //输入：
 //值（存储在数组v中）
 //权重（存储在数组w中）
 //不同项目的数量（n） 
 //背包容量（W）j从0到W的
 
做：
m [0，j]：= 0 
 
 for i从1到n做：从0到W的j的
做：如果w [i-1]< = j，则
然后：
m [i，j]：= max（m [i -1，j]，m [i-1，jw [i-1]] + v [i-1]）$ ​​b $ b else：
m [i，j]：= m [i-1， j] 
  

解决方案

感谢到@harold，看来这个问题不是背包问题，而是分区问题。我正在寻找的伪代码的一部分位于相应的Wikipedia页面中： https：//en.wikipedia。 org / wiki / Partition_problem

编辑：好吧，实际上，分区问题算法告诉您一组项目是否可以分为两组相等的值或不。假设它不能，您有一个近似算法，说您是否可以将集合分成2组，其差值小于 d 。
但他们没有告诉您所产生的子集，这就是我要寻找的。

我最终在这里找到一个问题（此处：平衡分区），并提供了我已经测试过并且可以正常工作的代码示例。

I'm working on a program to solve a variant of the 0/1 Knapsack problem.

The original problem is described here: https://en.wikipedia.org/wiki/Knapsack_problem. In case the link goes missing in the future, I will give you a summary of the 0/1 Knapsack problem (if you are familiar with it, jump this paragraph): Let's say we have n items, each with weight wi and value vi. We want to put items in a bag, that supports a maximum weight W, so that the total value inside the bag is the maximum possible without overweighting the bag. Items cannot have multiple instances (i.e., we only have one of each). The objective of the problem is to maximize SUM(vi.xi) so that SUM(wi.xi) <= W and xi = 0, 1 (xi represents the state of an item being or not in the bag).

For my case, there are small differences in both conditions and objective:

• The weight of all items is 1, wi = 1, i = 1...n

• I always want to put exactly half the items in the bag. So, the maximum weight capacity of the bag is half (rounded up) of the number of items.W = ceil[n/2] or W = floor[(n+1)/2].

• Also, the weight inside the bag must be equal to its maximum capacity SUM(wi.xi) = W

Finally, instead of maximizing the value of the items inside the bag, the objective is that the value of the items inside is as close as possible to the value of the items outside. Hence, my objective is to minimize |SUM(vi.-xi) - SUM[vi(1-xi)]|, which simplifies into something like minimize |SUM[vi(2xi - 1)]|.

Now, there is a pseudo-code for the original 0/1 Knapsack problem in the Wikipedia page above (you can find it on the bottom of this text), but I am having trouble adapting it to my scenario. Can someone help? (I am not asking for code, just for an idea, so language is irrelevant)

Thanks!

---

Wikipedia's pseudo-code for 0/1 Knapsack problem:

Assume w1, w2, ..., wn, W are strictly positive integers. Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i (first i items).

We can define m[i,w] recursively as follows:

• m[0, w]=0
• m[i, w] = m[i-1, w] if wi > w (the new item is more than the current weight limit)
• m[i, w]= max(m[i-1, w], m[i-1, w-wi] + vi) if wi <= w.

The solution can then be found by calculating m[n,W].

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
    m[0, j] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i-1] <= j then:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])
        else:
            m[i, j] := m[i-1, j]

解决方案

Thanks to @harold, it seems like this problem is not a Knapsack problem, but a Partition problem. Part of the pseudo-code I was seeking is in the corresponding Wikipedia page: https://en.wikipedia.org/wiki/Partition_problem

EDIT: well, actually, Partition problem algorithms tell you whether a Set of items can be partitioned in 2 sets of equal value or not. Suppose it can't, you have approximation algorithms, which say whether you can have the set partiotioned in 2 sets with the difference their values being lower than d. BUT, they don't tell you the resulting sub-sets, and that's what I was seeking.

I ended up finding a question here asking for that (here: Balanced partition), with a code example which I have tested and works fine.

这篇关于背包的变种的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！