0/1 Knapsack problem solver code

  • Updated on 5th Oct 2019

Table of Contents

This post only shows the correct source code which solving 0/1 knapsack prolem.

I hope the source code could be helpful to you.

Example

In this post, one example is listed:

Maximum capacityThe number of items
103
WeightValue
34
45
56

Source Code

The source code is as follows:

#include <iostream>

using namespace std;

int main() {
  const int N = 3;              // the number of items
  const int Capacity = 10;      // the volumn of knapsack
  int weight[N + 1] = {-1, 3, 4, 5}; // the volumn of i-th item (index starting from 1)
  int value[N + 1] = {-1, 4, 5, 6};  // the value of i-th item
  int F[N + 1][Capacity + 1] = {0};  // status

  for (int i = 1; i <= N; i++) { // as for i-th item
    for (int j = 0; j <= Capacity; j++) {
      F[i][j] = F[i - 1][j]; // do not choose i-th item (default)
      if (j - weight[i] >= 0 &&
          F[i][j] < F[i - 1][j - weight[i]] + value[i]) { // if value is higher, then choose i-th item
        F[i][j] = F[i - 1][j - weight[i]] + value[i];
      }
    }
  }

  cout << "Max value: " << F[N][Capacity] << endl; // in this case: 11

  cout << "Status: " << endl;
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= Capacity; j++) {
        printf("%2d ", F[i][j]);
    }
    cout << endl;
  }

  return 0;
}

Result

Max value: 11
Status:
 0  0  0  0  0  0  0  0  0  0  0
 0  0  0  4  4  4  4  4  4  4  4
 0  0  0  4  5  5  5  9  9  9  9
 0  0  0  4  5  6  6  9 10 11 11