Given a sequence of values/weights the program finds the collection of items which will lead to the largest value without going over the weight limit.

Knapsack.cpp

/**********************************************
Knapsack Problem
Alex Marroquin
12 March 2014

Given a sequence of problems and maximum weight
the objective is to find the collection of 
items which will add up to the highest value
while remaining under the weight limit.
**********************************************/

#include <iostream>

using namespace std;

const int item_cnt = 28;
const int max_num = 595;
int array2D[item_cnt+1][max_num+1];

void printR(int *a, int size)
{
	for(int i = 0; i < size; i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}


void initialize()
{
	for(int i = 0; i <= item_cnt+1; i++)
		for(int j = 0; j < max_num+1; j++)
			array2D[i][j] = 0;

}

int knapsack(int *a)
{
	int maxn = 0;
	for(int i = 1; i < item_cnt; i++)
	{
		for(int j = 1; j < max_num; j++)
		{
			if(a[i-1] <= j && a[i-1] + array2D[i-1][j-a[i]] <= 595)
				array2D[i][j] = max(array2D[i-1][j],a[i-1] + array2D[i-1][j-a[i-1]]);
			else
				array2D[i][j] = array2D[i-1][j];
			if(maxn < array2D[i][j])
				maxn = array2D[i][j];
		}
	}
	cout<<"Max value: "<<maxn<<endl;
	return 0;
}

void retrace(int p1, int p2, int *a)
{
	if(p2 <= 0)
		return;
	int x = array2D[p1-1][p2];
	
	if(x == array2D[p1][p2])
	{
		retrace(p1-1,p2,a);
	}
	else
	{
		cout<<a[p1-1]<<" ";
		retrace(p1-1,p2-a[p1-1],a);
	}
	
}

int *setArray(int *a)
{
	a = new int[28];
	a[0] = 5;
	a[1] = 23;
	a[2] = 27;
	a[3] = 37;
	a[4] = 48;
	a[5] = 51;
	a[6] = 63;
	a[7] = 67;
	a[8] = 71;
	a[9] = 75;
	a[10] = 79;
	a[11] = 83;
	a[12] = 89;
	a[13] = 91;
	a[14] = 101;
	a[15] = 112;
	a[16] = 121;
	a[17] = 132;
	a[18] = 137;
	a[19] = 141;
	a[20] = 143;
	a[21] = 147;
	a[22] = 153;
	a[23] = 159;
	a[24] = 171;
	a[25] = 181;
	a[26] = 190;
	a[27] = 191;

	return a;
}

int main()
{
	int *a = new int;
	a = setArray(a);
	printR(a, 28);
	initialize();
	knapsack(a);
	cout<<"The final value: "<<array2D[item_cnt-1][max_num-1]<<endl;
	cout<<"The number sequence is: ";
	retrace(item_cnt-1,max_num-1,a);
	cout<<endl;
	system("pause");
	return 0;
}