ZeroJudge B184: 裝貨櫃問題

現在一共有若干項貨品可選擇運載，每一項k都有一個已知的體積 v[k]，以及載運的利潤 c[k]，但是貨櫃的總容量是 100，可能無法將貨物全部裝入，希望選出其中的若干項，其體積總和不超過 100，使得利潤最大。（每一項貨物的體積為 1~100 的整數，而利潤是 1~60000 的整數。）

範例測資

範例輸入範例輸出
EOF 輸入，第一行是貨品數量，接下來每行各有兩筆數據，第一筆代表各項貨物的體積，第二筆代表各項貨物的利潤。輸出最大的利潤，例如輸出一、二項：第一項貨物的體積為 30，利潤為 60，第二項貨物的體積為 20，利潤為 50。
4
30 60
20 50
35 40
60 70
10
80 88
33 66
13 26
77 150
95 195
45 90
8 16
20 41
40 13
68 20		150
198

解題思路

使用 01 背包的概念來思考這題。只是要將目前重量的價值存到 Map 中。如果有遇到可以成對的數字，則要將兩個數字的 Map 值存放到兩的數字和的 Map 值中。

最後，從 100 往下找到第一個大於 0 的 Map 值並輸出。

範例程式碼－ZeroJudge B184: 裝貨櫃問題

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N) {
        unordered_map<int, int>MAP;
        vector<pair<int, int>> v;
        for (int i = 0; i<N; i++) {
            int a, b;
            cin >> a >> b;
            v.push_back(make_pair(a, b));
        }
        for (int i = 0; i<N; i++) {
            const int weight = v[i].first;
            for (int j = 100; j>=weight; j--) {
                if (MAP[j-weight] >= 0) {
                    MAP[j] = max(MAP[j], MAP[j-weight]+v[i].second);
                }
            }
            MAP[weight] = max(MAP[weight], v[i].second);
        }
        for (int i = 100; i>=100; i--) {
            if (MAP[i] >= 0) {
                cout << MAP[i] << "\n";
                break;
            }
        }
    }
}

//ZeroJudge B184
//Dr. SeanXD
標籤

相關文章

發佈留言