ZeroJudge A455: 商品特賣問題

在一個年終大拍賣活動中，一家迪化街的商店推出了一個特賣活動，老闆說只要你花錢買 4 個箱子，第一個箱子最多可裝 30 公斤的商品，第二個箱子最多可裝 40 公斤的商品，第三個箱子最多可裝 50 公斤的商品，第四個箱子最多可裝 25 公斤的商品。可以挑選的商品有十種，重量分別是 15、16、30、18、19、20、21、25、24、及 17 公斤。每一種商品最多只能挑一次，且一種商品不可拆開分到不同箱子中。假設產品加總的重量小於等於箱子的限定重量就一定裝得下這些產品，由於每樣產品的售價一樣，因此若挑選能裝入 4 個箱子的商品種類愈多，便表示價值愈高。請你寫一個程式來算出最多可以裝入這些箱子的商品數目，以便估算是否划算。

範例測資

範例輸入範例輸出
第一行為兩個整数 M 及 N 以空白區分，其中 M 表示箱子的個數，而 N 表示商品的種類數。
第二行開始的 M 行各為每一個箱子可容納的最大重量 (公斤)。從第 M+2 行開始的 N 行，則分別表示N種商品個別的重量 (公斤) 。
其中 0 < M ≤ 50，0 < N ≤ 1000。		顯示最多能够裝入這些箱子的商品數目。若找不到能裝入這些箱子的商品，請輸出 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 範例測資

解題思路

計算所有箱子的承載重量總和，並且將物品進行排序。將物品依序相加並且判斷是否會超過最大承載量，如果會的話就停止迴圈，並且要紀錄目前相加到第幾樣商品。

宣告一個回傳值為 bool 的 DFS，並且預設參數為兩個 int，分別為 num 和 box，代表目前要拿的物品序列號和要從哪一個箱子開始進行判斷。

在 DFS 中，對所有箱子進行判斷，如果目前的 num 商品塞得下這個箱子，則將商品塞到這個箱子看看，並且再次呼叫 DFS，只是這次 num 要 -1，並且 box 要使用 i，也就是目前跑到的箱子編號。如果這個 DFS 回傳值為 true，則可以在還原剛剛塞的商品後直接 return true。

如果呼叫 DFS 時發現 num < 0，代表已經把所有商品都判斷過了，就可以 return true。然後，要宣告一個 int start = 0，如果 box > 0 && items[num] == items[num+1]，代表目前商品和上一個商品大小一樣且已經有判斷過商品了，就將 start 設為 box，並且在判斷所有箱子時，將 For迴圈 的起點改成 start。

跑一個從 0 到 N-1 的 For迴圈，並且判斷 DFS(i+1, 0) 是否為 true，如果不成立就將迴圈 break，答案就是 i+1。

範例程式碼－ZeroJudge A455: 商品特賣問題

#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
標籤

相關文章

發佈留言