ACM 624 CD

0/1 KnapSack

最後一組測資輸出43 2也算對
其實我是看演算法筆記的Code才寫出來的，所以這份Code根本和網站上面的根本就一模一樣

解釋一下怎麼得到一組解答好了...
這邊的符號都是沿用演算法筆記裡面KnapSack Problem的符號
令Ans(n, w)表示C(n, w)的一組解答
我們會發現Ans(n, w) = Ans(n-1, w) || Ans(n-1, w-weight[n]) + weight[n]
這邊的"+"並非代表加法，而是解答的連接
所以我們可以用表格table紀錄，如果在計算Ans(n, w)時我們選擇了"放"，那我們就在table[n][w]紀錄weight[n]；如果選擇"不放"，那就在table[n][w]紀錄-1來代表我們沒放東西。其實還有一個紀錄的方法就是如果選擇"放"，我們就紀錄A代表我們選擇"放"的情況；反之，用B來代表"不放"，也就是"記錄過程" (可以參考ItoA的Dynamic Programming章節的Assembly Line)，至於輸出的方法請參考Code (Code是用第二種紀錄方法)。

第二份Code是我真的搞懂以後覺得自己"應該"寫出的Code，因為第一份輸出的迴圈以我目前的能力應該還想不出來，我只會想到遞迴= =+ 話說好像很多找解答的DP做法都是紀錄過程？


Code #1

#include <stdio.h>
#include <stdbool.h>

#define MAXTIME 10001

bool take[20][MAXTIME];

int main(void)
{
    int i, j, N, num, dur[20], time[MAXTIME];
   
    while (scanf("%d", &N) == 1)
    {
        scanf("%d", &num);
        for (i = 0; i < num; i++)
            scanf("%d", &dur[i]);
       
        for (j = 0; j <= N; j++)
            time[j] = 0;
        for (i = 0; i < num; i++)
            for (j = 0; j <= N; j++)
                take[i][j] = false;
        for (i = num-1; i >= 0; i--)
            for (j = N; j >= dur[i]; j--)
                if (time[j] < time[j-dur[i]]+dur[i])
                {
                    time[j] = time[j-dur[i]]+dur[i];
                    take[i][j] = true;
                }

        for (i = 0, j = N; i < num; i++)
            if (take[i][j])
            {
                printf("%d ", dur[i]);
                j -= dur[i];
            }
        printf("sum:%d\n", time[N]);
    }
   
    return 0;
}




Code #2

#include <stdio.h>
#include <stdbool.h>

#define MAXTIME 10001

bool take[20][MAXTIME];
int dur[20];

void print(int n, int w)
{
    if (n == 0)
    {
        if (take[0][w])
            printf("%d ", dur[0]);
        return;
    }
   
    if (take[n][w])
    {
        print(n-1, w-dur[n]);
        printf("%d ", dur[n]);
    }
    else
        print(n-1, w);
}

int main(void)
{
    int i, j, N, num, time[MAXTIME];
   
    while (scanf("%d", &N) == 1)
    {
        scanf("%d", &num);
        for (i = 0; i < num; i++)
            scanf("%d", &dur[i]);
       
        for (j = 0; j <= N; j++)
            time[j] = 0;
        for (i = 0; i < num; i++)
            for (j = 0; j <= N; j++)
                take[i][j] = false;
        for (i = 0; i < num; i++)
            for (j = N; j >= dur[i]; j--)
                if (time[j] < time[j-dur[i]]+dur[i])
                {
                    time[j] = time[j-dur[i]]+dur[i];
                    take[i][j] = true;
                }

        print(num-1, N);
        printf("sum:%d\n", time[N]);
    }
   
    return 0;
}