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. We need to find an optimum subset of items such that total value of selected items is maximum and the total weight of items is less than or equal to W.
Problem statement
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.
Read more here: Knapsack Problem (Dynamic Programming)
Code Implementation
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 (Pseudocode)
Let i = n, w = W, res = K[n][W] if res != K[i-1][w] mark the ith row in knapsack w = w - wti res = res - vali 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 (ith) 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