ZeroJudge B184: Container Loading Problem

Currently, there are several items available for transportation. Each item k has a known volume v[k] and a profit c[k]. However, the total capacity of the container is 100, which may not be enough to accommodate all the items. The goal is to select a subset of the items such that the total volume does not exceed 100 while maximizing the total profit. (The volume of each item is an integer between 1 and 100, and the profit is an integer between 1 and 60,000.)

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input uses EOF (End of File) format. The first line specifies the number of items. Each subsequent line contains two pieces of data: the first represents the volume of the item, and the second represents the profit of the item.Output the maximum profit. For example, if the first and second items are selected:
•The volume of the first item is 30, and the profit is 60.
•The volume of the second item is 20, and the profit is 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

Thought Process

Use the concept of the 0/1 knapsack problem to approach this question. The key is to store the current weight’s value in a Map. If you encounter a pair of numbers that can combine, you need to update the value of the sum of these two numbers in the Map.

Finally, iterate downward from 100 to find the first Map value greater than 0, and output it.

Sample Code－ZeroJudge B184: Container Loading Problem

#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
Tags

Related Posts

Comments