Lösung zu Blatt 2 (Aufgabe 2): knapsack.h + knapsack.c

knapsack.h

/*
 *      knapsack.h      - header file for some knapsack search function
 *
 *      Martin Hasch, University of Ulm, April 1997
 */

#include        "typedef.h"

/*
 *      Return largest possible key; smallest is zero.
 */
Key ks_maxkey(void);

/*
 *      Search for a key yielding the given code within [min...max].
 *      Return 1 and in *result the key in case of success, otherwise 0.
 */
int knapsack(Code code, Key min, Key max, Key *result);

knapsack.c

/*
 *      knapsack.c      - some knapsack search function
 *
 *      Martin Hasch, University of Ulm, April 1997
 */

#include        "typedef.h"
#include        "knapsack.h"

#define NITEMS  24
#define MAXKEY  ((1 << NITEMS) - 1)

static Code items[NITEMS] = {
        3141592,
        6535897,
        9323846,
        2643383,
        2795028,
        8419716,
        9399375,
        1058209,
        7494459,
        2307816,
        4062862,
         899862,
        8034825,
        3421170,
        6798214,
        8086513,
        2823066,
        4709384,
        4609550,
        5822317,
        2535940,
        8128481,
        1174502,
        8410270,
};

/*
 *      return largest possible key; smallest is zero.
 */
Key ks_maxkey(void)
{
        return MAXKEY;
}

/*
 *      Search for a key yielding the given code within [min...max].
 *      Return 1 and in *result the key in case of success, otherwise 0.
 */
int knapsack(Code code, Key min, Key max, Key *result)
{
        register Code sum;
        register Code *item;
        register Key aux, key;

        if ( max > MAXKEY )
                max = MAXKEY;

        for ( key=min; key<=max; ++key ) {
                sum = 0;
                item = items, aux = key;
                while ( aux && sum < code ) {
                        if ( aux & 1 )
                                sum += *item;
                        ++item, aux >>= 1;
                }
                if ( sum == code && !aux ) {
                        *result = key;
                        return 1;
                }
        }
        return 0;
}