/*
 * a knapsack 0/1 algorithm
 */

/*
 * Copyright (c) 2005 Andreas Jaggi <andreas.jaggi@waterwave.ch>
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdio.h>
#include <stdlib.h>

int** knapsack01(int *w, int *v, size_t n, int W, int *V);

int main ( int argc, char *argv[] ) {
	int V,i;
	int **c = (int**) NULL;
	int *w = (int*) NULL;
	int *v = (int*) NULL;
	int n = 5;
	int W = 6;

	w = (int*) malloc(sizeof(int)*n);
	v = (int*) malloc(sizeof(int)*n);

	v[0] = 6;
	v[1] = 10;
	v[2] = 12;
	v[3] = 19;
	v[4] = 21;

	w[0] = 6;
	w[1] = 5;
	w[2] = 4;
	w[3] = 3;
	w[4] = 12;

	c = knapsack01(w, v, n, W, &V);

	printf("%d\n", V);

	free(w);
	free(v);

	for ( i = 0; i <= n; i++ ) {
		free(*(c+i));
	}
	
	free(c);

	exit(0);
}

int** knapsack01(int *w, int *v, size_t n, int W, int *V) {
	int i,j;
	int **c = (int**) NULL;

	c = (int**) malloc(sizeof(int*)*(n+1));
	*c = (int*)malloc(sizeof(int)*(W+1));

	for ( i = 0; i <= W; i++ ) {
		c[0][i] = 0;
	}

	for ( i = 1; i <= n; i++ ) {
		*(c+i) = (int*)malloc(sizeof(int)*(W+1));

		c[i][0] = 0;

		for ( j = 1; j <= W; j++ ) {

			if ( *(w+i-1) <= j ) {
				if ( *(v+i-1) + c[i-1][j-*(w+i-1)] > c[i-1][j] ) {
					c[i][j] = *(v+i-1)+c[i-1][j-*(w+i-1)];
				} else {
					c[i][j] = c[i-1][j];
				}
			} else {
				c[i][j] = c[i-1][j];
			}
		}
	}

	*V = c[n][W];

	return c;
}