knapsack problem

knapsack01.c

#include <stdio.h>

#define NUM 8         // 製品の個数
#define MAX_WEIGHT 25 // ナップサックの容量

//       i = 0  1  2  3   4  5  6  7
int w[8] = { 3, 5, 4, 2, 10, 7, 1, 5 }; // 製品の容量
int v[8] = { 3, 7, 6, 3, 13, 9, 2, 6 }; // 製品の利得

// i番目以降の製品で, 容量uの制限があるときの最大利得を返す
int search(int i, int u, int *c)
{
    if (i == NUM) { // i = 8 は存在しないので 0 を返す
        return 0;
    }
    else if (u < w[i]) { // もしナップサックに入らないなら次の組み合わせに進む
        int nc = *c;
        int val = search(i + 1, u, &nc);
        *c = nc;

        return val;
    }
    else {
        int c1 = *c;
        int val1 = search(i + 1, u, &c1); // i番目の製品を入れなかった場合

        int c2 = *c | (1 << i);
        int val2 = v[i] + search(i + 1, u - w[i], &c2); // i番目の製品を入れた場合

        if (val1 < val2) {
            *c = c2;
            return val2;
        } else {
            *c = c1;
            return val1;
        }
    }
}

int main(int argc, const char * argv[])
{
    int combination = 0;
    int max_value = search(0, MAX_WEIGHT, &combination);

    printf("max_value: %d\n", max_value);

    for (int i = 0; i < NUM; i++) {
        int result = combination & (1 << i);

        if (result == 0) {
            printf("%d: 入れない\n", i);
        } else {
            printf("%d: 入れる\n", i);
        }
    }

    return 0;
}

knapsack02.c

#include <stdio.h>

#define NUM 8         // 製品の個数
#define MAX_WEIGHT 25 // ナップサックの容量

//       i = 0  1  2  3   4  5  6  7
int w[8] = { 3, 5, 4, 2, 10, 7, 1, 5 }; // 製品の容量
int v[8] = { 3, 7, 6, 3, 13, 9, 2, 6 }; // 製品の利得

int get_weight(int *c)
{
    int weight = 0;

    for (int i = 0; i < NUM; i++) {
        if (c[i] == 1) {
            weight += w[i];
        }
    }

    return weight;
}

int get_value(int *c)
{
    int value = 0;

    for (int i = 0; i < NUM; i++) {
        if (c[i] == 1) {
            value += v[i];
        }
    }

    return value;
}

int search3(int *ret)
{
    int combination[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; // これからいろんな組み合わせを試していくんやけど, それを保持する変数や

    int max_value = 0; // 最大の利得
    int max_combination[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; // 最大の利得を得られる組み合わせ

    // 入れるか入れないかが8個だから組み合わせは256通り
    for (int i = 0; i < 256; i++) {
        // iを2進数に変換(結果は配列flagに入る)
        int temp = i;
        for (int j = 0; j < NUM; j++) {
            combination[j] = temp % 2;
            temp = temp / 2;
        }

        // もし, 容量オーバーしていたら次の組み合わせに移る
        if (get_weight(combination) > MAX_WEIGHT) {
            continue;
        }

        // 求めた組み合わせで得られる利得を計算する
        int value = get_value(combination);

        // もし今分かっている最大利得より大きければ
        if (value > max_value) {
            // 最大利得を更新する
            max_value = value;

            // 組み合わせを更新する(配列をコピーする)
            for (int j = 0; j < NUM; j++) {
                max_combination[j] = combination[j];
            }
        }
    }

    // 配列をコピーする
    for (int i = 0; i < NUM; i++) {
        ret[i] = max_combination[i];
    }

    return max_value;
}

int main(int argc, const char * argv[])
{
    int combination[NUM] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    int max_value = search3(combination);

    printf("max_value: %d\n", max_value);

    for (int i = 0; i < NUM; i++) {
        printf("%d: %d\n", i, combination[i]);
    }

    return 0;
}

knapsack03.c

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

#define NUM 8         // 製品の個数
#define MAX_WEIGHT 25 // ナップサックの容量

//       i = 0  1  2  3   4  5  6  7
int w[8] = { 3, 5, 4, 2, 10, 7, 1, 5 }; // 製品の容量
int v[8] = { 3, 7, 6, 3, 13, 9, 2, 6 }; // 製品の利得

int compare(const void *a_ptr, const void *b_ptr)
{
    int a_index = *((int *)a_ptr);
    int b_index = *((int *)b_ptr);

    int a_val = v[a_index] / w[a_index];
    int b_val = v[b_index] / w[b_index];

    if (a_val > b_val) {
        return -1;
    } else if (a_val == b_val) {
        return 0;
    } else {
        return 1;
    }
}

int main(int argc, const char * argv[])
{
    // リストを作る
    float list[8];
    for (int i = 0; i < NUM; i++) {
        list[i] = (float)v[i] / (float)w[i];
    }

    // リストを表示
    printf("list:\n");
    for (int i = 0; i < NUM; i++) {
        printf("%d: %f\n", i, list[i]);
    }

    // 価値の高い順にソートする(クイックソート)
    int indexes[NUM] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    qsort((void *)indexes, NUM, sizeof(int), compare);

    // ソート後のリストを表示
    printf("list (sorted):\n");
    for (int i = 0; i < NUM; i++) {
        printf("%d: %f (%d)\n", i, list[indexes[i]], indexes[i]);
    }

    // 価値の高い順に入れれるかどうかを試していく
    int combination[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    int weight = 0;
    int value = 0;
    for (int i = 0; i < NUM; i++) {
        int index = indexes[i];

        if (weight + w[index] <= MAX_WEIGHT) {
            combination[index] = 1;
            weight += w[index];
            value += v[index];
        }
    }

    // 結果を出力
    printf("value: %d\n", value);
    printf("weight: %d\n", weight);

    for (int i = 0; i < NUM; i++) {
        printf("%d: %d\n", i, combination[i]);
    }

    return 0;
}