打印 0/1 背包问题中的物品

给定 n 个物品的重量和价值，我们将这些物品放入一个容量为 W 的背包中，以获得背包内的最大总价值。换句话说，给定两个整数数组，val[0..n-1] 和 wt[0..n-1]，分别代表 n 个物品的价值和重量。同时给定一个整数 W 代表背包容量，我们需要找到这样一个物品子集：其重量之和小于或等于 W。注意我们不能拆分物品，要么完整地选取物品，要么不选（0-1 属性）。

前置知识： 0/1 背包问题
示例：

输入 : val[] = {60, 100, 120};
        wt[] = {10, 20, 30};
        W = 50;
输出 : 220 // 可以获得的最大价值
         30 20 // 包含了重量为 20 和 30 的物品。

输入 : val[] = {40, 100, 50, 60};
        wt[] = {20, 10, 40, 30};
        W = 60;
输出 : 200
         30 20 10

方法：

假设 val[] = {1, 4, 5, 7}, wt[] = {1, 3, 4, 5}，W = 7。

二维背包表将如下所示：

!2d knapsack table

让我们从 K[n][W] 开始回溯。这里的 K[n][W] 是 9。

由于这个数值来自上方（如灰色箭头所示），因此这一行对应的物品没有被包含。我们在表中垂直向上移动，不将该物品放入背包。现在，这个数值 K[n-1][W] 为 9，它并非来自上方，这意味着这一行对应的物品被包含了，我们需要垂直向上移动，并向左移动被包含物品的重量（如黑色箭头所示）。继续这个过程，我们将重量为 3 和 4 的物品包含在背包中，其总价值为 9。

C++


CODEBLOCK_8ebd09ba


C


“

// CPP code for Dynamic Programming based

// solution for 0-1 Knapsack problem

#include

// A utility function that returns maximum of two integers

int max(int a, int b) { return (a > b) ? a : b; }

// Prints the items which are put in a knapsack of capacity W

void printknapSack(int W, int wt[], int val[], int n)

{

int i, w;

int K[n + 1][W + 1];

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++) {

for (w = 0; w <= W; w++) {

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i – 1] <= w)

K[i][w] = max(val[i – 1] +

K[i – 1][w – wt[i – 1]], K[i – 1][w]);

else

K[i][w] = K[i – 1][w];

}

}

// stores the result of Knapsack

int res = K[n][W];

printf("%d

", res);

w = W;

for (i = n; i > 0 && res > 0; i–) {

// either the result comes from the top

// (K[i-1][w]) or from (val[i-1] + K[i-1]

// [w-wt[i-1]]) as in Knapsack table. If

// it comes from the latter one/ it means

// the item is included.

if (res == K[i – 1][w])

continue;

else {

// This item is included.

printf("%d ", wt[i – 1]);

// Since this weight is included its

// value is deducted

res = res – val[i – 1];

w = w – wt[i – 1];

}

}

}

// Driver code

int main()

{

int val[] = {