diff --git a/c/knapsack01.c b/c/knapsack01.c new file mode 100644 index 0000000..6644e50 --- /dev/null +++ b/c/knapsack01.c @@ -0,0 +1,109 @@ +/* + * a knapsack 0/1 algorithm + */ + +/* + * Copyright (c) 2005 Andreas Jaggi + * 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 +#include + +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; +}