knapsack problem

[algoman1]

Hello,
I implemented the knapsack problem in C++. it seems my final result is correct...but the intermediate result seem to be different when i display the entire 2d array...could someone give me some feedback on this?

#include <iostream>
#include <vector>
#include <array>
using namespace std;

const int n_size = 4;
const int w_size = 10;

int main() {
	// Knapsack Problem
	// Time Complexity: O(n*w), Space Complexity: O(n*w)

	// Values (stored in array v)
	// Weights (stored in array w)
	// Number of distinct items (n)
	// Knapsack capacity (W)

    	std::vector<int> v = {10, 40, 30, 50};
    	std::vector<int> w = {5, 4, 6, 3};
                              	   //columns //rows
	std::array<std::array<int, w_size+1>, n_size+1> A; 

	// initialization
	for(int w = 0; w <= w_size; w++) {
		A[0][w] = 0;
	}

	// main loop
	for(int i = 1; i <= n_size; i++) {
		for(int j = 0; j <= w_size; j++) {
			if(w[i] > j) {
				A[i][j] = A[i - 1][j];
			}
			else {
				A[i][j] = max(A[i - 1][j], v[i] + A[i - 1][j - w[i]]);
			}
		}
	}

	// display 2d array A
	for(int i = 0; i <= n_size; i++) {
		for(int j = 0; j <= w_size; j++) {
			cout << A[i][j] << " ";
		}
		cout << endl;
	}

	cout << endl;
	cout << A[n_size][w_size] << endl;

	return 0;
}

[aligatorman2]

It looks like the initialisation is wrong. Your code says, there is a knapsack weighting 10kg with 0 value. But obviously, such a knapsack doesn't exist. The standard hack around this is initializing everything except 0kg with INT_MIN:

#include <limits>

    // initialization
    A[0][0] = 0;
    for(int w = 1; w <= w_size; w++)
        A[0][w] = std::numeric_limits<int>::min();

Then, every state with value <0 means impossible.

(I recommend this hack, as it's much faster than a seperate bool array bool possible[w_size] since it's getting rid of the banching. And it should work just as fine.)