ZeroJudge A455: Commodity Sales

During a year-end sale, a shop on Dihua Street launched a special offer. The owner said that if you buy 4 boxes, the first box can hold up to 30 kg of goods, the second box up to 40 kg, the third box up to 50 kg, and the fourth box up to 25 kg. There are ten types of items to choose from, with weights of 15, 16, 30, 18, 19, 20, 21, 25, 24, and 17 kg. Each type of item can be chosen at most once, and an item cannot be split between different boxes. Assuming that the total weight of the items is less than or equal to the box's limit, they will fit in the boxes. Since each item has the same price, the more items that can be packed into the 4 boxes, the higher the value. Please write a program to calculate the maximum number of items that can be packed into these boxes to estimate if the deal is worthwhile.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line consists of two integers M and N separated by a space, where M represents the number of boxes and N represents the number of types of items.
Starting from the second line, the next M lines each represent the maximum weight (in kilograms) that each box can hold. From the (M+2)th line, the next N lines each represent the weight (in kilograms) of each type of item.
Where 0 < M ≤ 50, and 0 < N ≤ 1000.		Display the maximum number of items that can be packed into these boxes. If no items can be packed into the boxes, output 0.
4 10
30
40
50
25
15
16
30
18
19
20
21
25
24
17		7
3 9
20
10
10
3
8
3
7
9
3
5
8
5		7
ZeroJudge A455 Sample Test Cases

Thought Process

Calculate the total carrying capacity of all the boxes, then sort the items. Sum the items sequentially and check if the total exceeds the maximum carrying capacity. If it does, stop the loop and record the current item count.

Declare a DFS function that returns a boolean value, with two integer parameters: num and box, representing the current item index and the starting box index for checking.

In the DFS function, check all the boxes. If the current item num can fit in the box, place the item in the box and call DFS again, this time with num - 1 and the current box index i. If this DFS call returns true, restore the item to the previous state and return true.

If when calling DFS you find that num 0 and items[num] == items[num+1], it means the current item size is the same as the previous one and items have already been evaluated, so set start to box and adjust the starting point of the for loop in the box check to start.

Run a for loop from 0 to N-1, and check if DFS(i+1, 0) returns true. If it does not, break the loop, and the answer will be i+1.

Sample Code－ZeroJudge A455: Commodity Sales

#include <iostream>
#include <algorithm>
using namespace std;

int M, N, ans = 0;
int boxes[55] , items[1005];

bool DFS(const int num, const int box) {
    if(num < 0) return true;
    int start = 0;
    if(box > 0 && items[num] == items[num+1]) start = box;
    for (int i = start; i<M; i++) {
        const int item = items[num];
        if (boxes[i] - item >= 0) {
            boxes[i] -= item;
            if (DFS(num-1, i)) {
                boxes[i] += item;
                return true;
            }
            boxes[i] += item;
        }
    }
    return false;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> M >> N;
    int totalBNox = 0;
    for (int i = 0; i<M; i++) {
        cin >> boxes[i];
        totalBNox += boxes[i];
    }
    int totalWeight = 0;
    for (int i = 0; i<N; i++) {
        cin >> items[i];
    }
    sort(items, items+N);
    int i;
    for (i = 0; i<N; i++) {
        totalWeight += items[i];
        if(totalWeight > totalBNox) break;
        if(!DFS(i, 0)) break;
    }
    cout << i << "\n";
}

//ZeroJudge A455
//Dr. SeanXD
Tags

Related Posts

Comments