Getting an error while passing an array through a function

[philip92]

I have written an algorithm for 0-1 Knapsack Algorithm. I created an array based on the function inputs but I was getting an error "Expression must have a const value".

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int knapsack(int W, int wt[], int val[], int n)
{
	int i, w;
	int K[n + 1][W + 1]; //Getting an Error HERE

	// Build table K[][] in bottom up manner
	for (i = 0; i <= n; i++)
	{
		for (w = 0; w <= W; w++)
		{
			if (i == 0 || w == 0)
				K[i][w] = 0;
			else if (wt[i - 1] <= w)
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
			else
				K[i][w] = K[i - 1][w];
		}
	}

	return K[n][W];
}

int main()
{
	int val[] = { 60, 100, 120 };
	int wt[] = { 10, 20, 30 };
	int  W = 50;
	int n = sizeof(val) / sizeof(val[0]);
	int solution = knapsack(W, wt, val, n);
	cout << solution << endl;
	return 0;
}

[lastchance]

Replace that line by the rank-2 analogue with vectors:

vector< vector<int> > K( n + 1, vector<int>(W + 1) ); //No longer getting an Error HERE


You were trying to use a VLA (variable-length array): that would be legitimate in the C99 version of C and some other languages, but not in C++ (yet).

If you need to declare the size at run time then you will need to use either new (and delete), or, more conveniently, a vector for your arrays.

[philip92]

@lastchance, Thanks for the reply. So, is "vector< vector<int> > K( n + 1, vector<int>(W + 1) )" a 2d vector.

[lastchance]

Strictly, it's a "vector of vectors", or a "sequence of rows". To all intents and purposes here it behaves like a 2-d array.

C++ is not as simple for multi-dimensional arrays as other languages. (That's my opinion, anyway.)