louisfghbvc的部落格

問題描述 ：

小雅參加了一場量販店所舉辦的活動，活動內容為在有限的空間推車上，以不裝超過推車空間為原則，將量販店中所販賣的物品放置推車中，將推車內所有物品的價值總和為最大者，即為優勝者，並可將推車內所有物品回家，小雅希望能在活動中成為優勝者，請利用程式讓小雅能在這場活動中成為優勝者。

輸入說明 ：

第一列為推車最大負載空間，第二列為量販店所販賣的物品數量( n )，第三列到第n+2列為物品的大小、物品的價格、物品的名稱。(所有數字皆為正整數,且空間單位相同)

輸出說明 ：

印出一列為「Total: (總價), including (物品的數量) (物品的名稱)」，物品的名稱請以空格為間隔隔開並註明物品數量。（只要達到最高的價值總和即可，量販店中物品可隨意搭配，不要裝超過推車空間容量即可。）

範例 ：

思路: 無限背包, 紀錄放了哪些。本題dp[j] = max(dp[j], dp[j - w[i]] + c[i]) (放那個物品, 或者不放那個物品用原來的)

w 指重量, c 指獲利。然後如果值有更動, 就紀錄起來。從陣列右下方推回去, 可以得到字典序最小的序列 就是答案

代碼:

#include <iostream>
#include <map>

using namespace std;

int main()
{
    int weight, n;
    while(cin >> weight >> n){
        int w[n + 2], cost[n + 2];
        string name[n + 2];
        int dp[weight + 2] = {};
        bool dd[n + 2][weight + 2] = {};
        for(int i = 1; i <= n; ++i){
            cin >> w[i] >> cost[i] >> name[i];
        }
        for(int i = 1; i <= n; ++i){
            for(int j = w[i]; j <= weight; ++j){
                if(dp[j] < dp[j - w[i]] + cost[i]){
                    dp[j] = dp[j - w[i]] + cost[i];
                    dd[i][j] = true;
                }
            }
        }
        int tw = weight, e = n;
        map <string, int> mp;
        while(tw > 0){
            int i;
            for(i = e; i >= 0; --i){
                if(dd[i][tw]){
                    e = i;
                    break;
                }
            }
            if(i < 0)
                break;
            mp[name[e]]++;
            tw -= w[e];
        }
        cout << "Total: " << dp[weight] << ", including";
        for(int i = 1; i <= n; ++i){
            if(mp[name[i]])
                cout << " " <<mp[name[i]] << " " << name[i];
        }
        cout << endl;
    }
    return 0;
}