19

这里我有使用背包算法计算最优值的代码（装箱NP-hard问题）：

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for ( int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

我还需要显示包中包含的元素。我想创建一个数组来放置所选元素。所以问题是，我可以在哪一步执行这个选择？有没有其他更有效的方法来确定哪些项目已被拿走？

我希望能够知道给我最佳解决方案的项目，而不仅仅是最佳解决方案的价值。

4

4 回答 4

14

可以使用矩阵中的数据来获取您从矩阵中打包的元素，而无需存储任何额外的数据。

伪代码：

line <- W
i <- n
while (i > 0):
  if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
      // the element 'i' is in the knapsack
      i <- i-1 // only in 0-1 knapsack
      line <- line - weight(i)
  else: 
      i <- i-1

它背后的想法是迭代矩阵；如果重量差异恰好是元素的大小，则它在背包中。如果不是，则该物品不在背包中，继续没有它。

于 2011-09-20T17:51:21.997 回答
2 
line <- W
i <- n
while (i> 0):
  if dp[line][i] - dp[line - weight(i) ][i-1] == value(i):
    the element 'i' is in the knapsack
    cw = cw - weight(i)
    i <- i-1
  else if dp[line][i] > dp[line][i-1]:
    line <- line - 1
  else: 
    i <- i-1

只需记住添加项目 i 时如何到达 dp[line][i]

dp[line][i] = dp[line - weight(i) ][i - 1] + value(i);
于 2012-07-30T22:29:31.150 回答
1

重建有界 0/1 背包中的物品的算法比该线程中的一些现有代码更简单，这可能会让人们相信。这个答案旨在稍微揭开这个过程的神秘面纱，并提供一个干净、直接的实现以及一个工作示例。

该方法

从与表轴相对应的两个索引开始：一个weight初始化为背包容量的变量和一个i沿项目轴在 DP 查找表上向后循环的索引，在索引 1 处停止（算法使用i-1因此在 1 处停止以避免越界使用权）。

在循环中， if T[weight][i] != T[weight][i-1]，将 item 标记i-1为选中，减去其权重并继续沿 item 轴向后退。

重构的时间复杂度为O(length(items))。

这是 Python 作为伪代码：

def reconstruct_taken_items(T, items, capacity):
    taken = []
    weight = capacity

    for i in range(len(items), 0, -1): # from n downto 1 (inclusive)
        if T[weight][i] != T[weight][i-1]:
            taken.append(items[i-1])
            weight -= items[i-1].weight

   return taken

例子

例如，考虑一个背包容量为 9 和这些物品：

[item(weight=1, value=2), 
 item(weight=3, value=5), 
 item(weight=4, value=8), 
 item(weight=6, value=4)]

通过取项目 0、1 和 2，最佳值是 15。

DP查找表是

items ---->

0  1  2  3  4
--------------+
0  0  0  0  0 | 0  capacity
0  2  2  2  2 | 1     |
0  2  2  2  2 | 2     |
0  2  5  5  5 | 3     v
0  2  7  8  8 | 4
0  2  7 10 10 | 5
0  2  7 10 10 | 6
0  2  7 13 13 | 7
0  2  7 15 15 | 8
0  2  7 15 15 | 9

在此运行重建算法：

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15 <-- weight = capacity = 9
        ^   ^
        |   |
      i-1   i = length(items) = 4

在上面的初始状态中，T[weight][i] == T[weight][i-1]( 15 == 15) 所以item[i-1]( item(weight=6, value=4)) 没有被采用。减少i并尝试具有相同容量的剩余项目。

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15 <-- weight = 9
        ^
        |
        i = 3

在这里，T[weight][i] != T[weight][i-1]( 7 != 15) so items[i-1]，即items[2]， 或item(weight=4, value=8)，必须被取走。将剩余重量减items[i-1].weight, 或,取出图片9 - 4 = 5后尝试剩余重量较小的物品。item[i-1]

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10 <-- weight = 5
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15
      ^
      |
      i = 2

在这种状态下，我们又得到了T[weight][i] != T[weight][i-1]( 2 != 7)，所以我们必须取items[i-1]，即items[1]，或item(weight=3, value=5)。将剩余重量减少items[i-1].weight、 或5 - 3，然后移至下一项。

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2 <-- weight = 2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15
   ^
   |
   i = 1

在这最后一步中，我们又得到了T[weight][i] != T[weight][i-1]( 0 != 2)，所以我们一定有items[i-1]，即items[0]，或item(weight=1, value=2)。将剩余的权重减少items[i-1].weight, 或2 - 1，然后退出循环，因为i == 0.

C++ 实现

#include <iostream>
#include <vector>

class Knapsack {
public:
    struct Item {
        const int weight;
        const int value;
    };

private:
    static std::vector<Item> reconstruct_taken_items(
        const std::vector<std::vector<int> > &T,
        const std::vector<Item> &items,
        const int capacity
    ) {
        std::vector<Item> taken;
        int weight = capacity;
    
        for (size_t i = items.size(); i > 0; i--) {
            if (T[weight][i] != T[weight][i-1]) {
                taken.emplace_back(items[i-1]);
                weight -= items[i-1].weight;
            }
        }
    
        return taken;
    }

public:
    static std::vector<Item> solve(
        const std::vector<Item> &items, 
        const int capacity
    ) {
        std::vector<std::vector<int> > T(
            capacity + 1,
            std::vector<int>(items.size() + 1, 0)
        );
        
        for (int i = 1; i <= capacity; i++) {
            for (size_t j = 1; j <= items.size(); j++) {
                const Item &item = items[j-1];

                if (item.weight > i) {
                    T[i][j] = T[i][j-1];
                }
                else {
                    T[i][j] = std::max(
                        T[i-item.weight][j-1] + item.value, 
                        T[i][j-1]
                    );
                }
            }
        }
        
        return reconstruct_taken_items(T, items, capacity);
    }
};

int main() {
    const int capacity = 9;
    const std::vector<Knapsack::Item> items = {
        {1, 2}, {3, 5}, {4, 8}, {6, 4}
    };

    for (const Knapsack::Item &item : Knapsack::solve(items, capacity)) {
        std::cout << "weight: " << item.weight 
                  << ", value: " << item.value << "\n";
    }

    return 0;
}

也可以看看

于 2021-02-12T14:53:38.980 回答
0

这是一个朱莉娅实现：

function knapsack!{F<:Real}(
    selected::BitVector,    # whether the item is selected
    v::AbstractVector{F},   # vector of item values (bigger is better)
    w::AbstractVector{Int}, # vector of item weights (bigger is worse)
    W::Int,                 # knapsack capacity (W ≤ ∑w)
    )

    # Solves the 0-1 Knapsack Problem
    # https://en.wikipedia.org/wiki/Knapsack_problem
    # Returns the assigment vector such that
    #  the max weight ≤ W is obtained

    fill!(selected, false)

    if W ≤ 0
        return selected
    end

    n = length(w)
    @assert(n == length(v))
    @assert(all(w .> 0))

    ###########################################
    # allocate DP memory

    m = Array(F, n+1, W+1)
    for j in 0:W
        m[1, j+1] = 0.0
    end

    ###########################################
    # solve knapsack with DP

    for i in 1:n
        for j in 0:W
            if w[i] ≤ j
                m[i+1, j+1] = max(m[i, j+1], m[i, j-w[i]+1] + v[i])
            else
                m[i+1, j+1] = m[i, j+1]
            end
        end
    end

    ###########################################
    # recover the value

    line = W
    for i in n : -1 : 1
        if line - w[i] + 1 > 0 && m[i+1,line+1] - m[i, line - w[i] + 1] == v[i]
            selected[i] = true
            line -= w[i]
        end
    end

    selected
end
于 2015-10-14T23:07:46.313 回答