演算法 0-1 Double Knapsack Problem

#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
    int c[101], w[101], v[101];
    static int result[101][1001][1001] = {0}; //建空表格
    int N, W, V;
    scanf_s("%d%d%d", &N, &W, &V);
    for (int i = 1; i <= N; i++) {
        scanf_s("%d", &c[i]);//商品的價值
    }
    for (int i = 1; i <= N; i++) {
        scanf_s("%d", &w[i]);//商品的重量
    }
    for (int i = 1; i <= N; i++) {
        scanf_s("%d", &v[i]);//商品的體積
    }

    //填入表格
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= W; i++) {
            for (int j = 1; j <= V; j++) {
                //放不下(重量過重 || 體積太大)
                if (i < w[k] || j < v[k])
                    result[k][i][j] = result[k - 1][i][j];
                //放得下，要不要放?
                else
                    result[k][i][j] = result[k - 1][i][j] > (c[k] + result[k - 1][i - w[k]][j - v[k]]) ? result[k - 1][i][j] : (c[k] + result[k - 1][i - w[k]][j - v[k]]);
            }
        }
    }

    //追溯選中的商品
    int bagw = W;
    int bagv = V;
    int total = 0;
    int get[101];
    //倒回去判斷
    for (int i = N; i >= 1; i--) {
        //如果在指定承重量下，該商品對應的收益和上一个商品對應的收益相同，表示沒選到該商品
        if (result[i][bagw][bagv] == result[i - 1][bagw][bagv]) {
            //沒事
        }
        //被選到了
        else {
            total++;
            get[total] = i; //被選到的商品號碼
            bagw = bagw - w[i];//刪除被選到商品的重量體積
            bagv = bagv - v[i];
        }
    }


    printf("%d\n", result[N][W][V]); // 最大總價值
    printf("%d\n", total); // 選了幾個商品
    printf("(");

    if (total > 0) {
        printf("%d", get[total]);
    }
    for (int i = total - 1; i >= 1; i--) {
        printf(",%d", get[i]);
    }
    printf(")");

}