ACM: 990 – Diving for Gold

也是0/1 Knapsack Problem，要輸出最後「背包」放入物品的總價值、物品數量，和輸出被放入的所有物品。

CODE

#include <iostream>

enum { CAPACITY = 1000, TREASURE = 30 };

int main(){

    int t, w, n, d[TREASURE], td[TREASURE], v[TREASURE];

    int i, j, mval[CAPACITY+1], items[CAPACITY+1];

    bool grab[TREASURE][CAPACITY+1], flag = 0;

    while( scanf("%d%d%d", &t, &w, &n) != EOF ){

        for(i=0; i<n; ++i){

            scanf("%d%d", &d[i], &v[i]);

            td[i] = d[i] * 3 * w;

        }

        memset(mval, 0, sizeof(mval));

        memset(items, 0, sizeof(items));

        memset(grab, 0, sizeof(grab));

        for(i=n; i>=0; --i){

            for(j=t; j>=td[i]; --j){

                if( mval[j-td[i]]+v[i] > mval[j] ){

                    mval[j] = mval[j-td[i]] + v[i];

                    items[j] = items[j-td[i]] + 1;

                    grab[i][j] = 1;

                }

            }//j

        }//i

        if( flag ) printf("\n");

        else flag = 1;

        printf("%d\n%d\n", mval[t], items[t]);

        for(i=0, j=t; i<n; ++i){

            if( grab[i][j] ){

                printf("%d %d\n", d[i], v[i]);

                j -= td[i];

            }

        }

    }

    return 0;

}