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.
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