# Knapsack problem (Finding selected items)

In the last post, we learned about Knapsack problem and also found an efficient solution to the problem using Dynamic programming.

#### A little recap

Let given weights & values of n items to be put in a knapsack of capacity W ie.

We’ve 2 integer arrays value[0..n-1] and weight[0…n-1]. The objective is to find out the maximum value subset of value[] array such that sum of weight of subset is smaller or equal to W.

Problem statement

Read more here: Knapsack Problem (Dynamic Programming)

#### Our solution

Constructing a temporary array K[n][W] in bottom up manner.

int knapsack (int W, int wt[], int val[], int n) {
int K[n+1][W+1] = {0};

// Building table K[n][W] in bottom manner
for(int i=0; i<=n; i++) {
for(int w=0; w <= W; w++) {

// Base case: empty knapsack
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (wt[i-1] <= w) {

// Selecting val[i-1] if it gives higher knapsack value
K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
K[i-1][w]);
} else {

// Not including val[i-1]: if wt[i-1] is greater than
// available knapsack capacity
K[i][w] = K[i-1][w];
}
}
}
return K[n][W];
}


Time complexity of this solution is O(n*W).

#### Finding Actual Knapsack Items

Let i = n, w = W, res = K[n][W]

if res != K[i-1][w]
mark the i^th row in knapsack

w = w - wt_i
res = res - val_i
i = i-1;
else
i = i-1;  

The idea here is that in table K[n][W], if previous row maximum value is different than current row. It means that current (i^{th}) item was added in knapsack.

#include <iostream>
#include <cstdio>
using namespace std;
const int W = 3;
const int N = 3;

void printKnapsackTable (int K[][W+1]) {

printf("\nKnapsack Table\n");

for (int i=0; i<=N; i++) {
for (int j=0; j<=W; j++) {
printf("%d ", K[i][j]);
}
printf("\n");
}
}

void findKnapsackItems(int K[][W+1], int wt[], int val[]) {

int i=N, res=K[N][W], w=W;

printf("\nKnapsack Items:\n");

while (i>0 && res>0) {

if (res != K[i-1][w]) {

printf("%d - %d is selected\n", i, val[i-1]);

res = res - val[i-1];
w = w - wt[i-1];
}

i=i-1;
}
}

int knapsack (int wt[], int val[], int K[][W+1]) {

// Building table K[n][W] in bottom manner
for(int i=0; i<=N; i++) {
for(int w=0; w <= W; w++) {

// Base case: empty knapsack
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (wt[i-1] <= w) {

// Selecting val[i-1] if it gives higher knapsack value
K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
K[i-1][w]);
} else {

// Not including val[i-1]: if wt[i-1] is greater than available knapsack capacity
K[i][w] = K[i-1][w];
}
}
}
return K[N][W];
}

int main() {

int val[] = {60, 100, 120};
int wt[] = {1, 2, 1};
int K[N+1][W+1] = {0};

printf("Knapsack Value: %d", knapsack(wt, val, K));

printKnapsackTable(K);
findKnapsackItems(K, wt, val);

return 0;
}


Output

Knapsack Value: 220
Knapsack Table
0 0 0 0
0 60 60 60
0 60 100 160
0 120 180 220

Knapsack Items:
3 - 120 is selected
2 - 100 is selected

Here’s the working example: Knapsack Problem