演算法 Double Knapsack Problem

int main()
{
    int N, W, V, c[101], w[101], v[101];
    scanf("%d%d%d", &N, &W, &V);
    for (int k = 1; k <= N; k++) {
        scanf("%d", &c[k]);
    }
    for (int k = 1; k <= N; k++) {
        scanf("%d", &w[k]);
    }
    for (int k = 1; k <= N; k++) {
        scanf("%d", &v[k]);
    }

    static int result[101][1001][1001] = {0};
    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 total = 0;
    int bagw = W;
    int bagv = V;
    int get[101];

    for (int k = N; k >= 1; k--) {
        if (result[k][bagw][bagv] == result[k - 1][bagw][bagv]){}
        else {
            total++;
            get[total] = k;
            bagw -= w[k];
            bagv -= v[k];
        }
    }

    printf("%d\n", result[N][W][V]);
    printf("%d\n", total);
    printf("(");
    if (total > 0) {
        printf("%d", get[total]);
        for (int k = total - 1; k >= 1; k--) {
            printf(",%d", get[k]);
        }
    }
    printf(")");
}