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

Leave a Reply

Your email address will not be published.