回復 1# may - //#include <iostream>
- //#include <vector>
- //#include <algorithm>
- #include <bits/stdc++.h>
- using namespace std;
- struct Order {
- int id, time, value;
- };
- int main() {
- int N; // 訂單數量
- cin >> N;
- vector<Order> orders(N);
- for (int i = 0; i < N; i++) {
- cin >> orders[i].id >> orders[i].time >> orders[i].value;
- }
- int X; // 可用時間
- cin >> X;
- // 動態規劃陣列
- vector<int> dp(X + 1, 0);
- vector<vector<bool>> chosen(N + 1, vector<bool>(X + 1, false));
- // 記錄選擇的訂單
- vector<vector<int>> track(N + 1, vector<int>(X + 1, -1));
- // 動態規劃求最大收益
- for (int i = 0; i < N; i++) {
- for (int j = X; j >= orders[i].time; j--) {
- if (dp[j - orders[i].time] + orders[i].value > dp[j]) {
- dp[j] = dp[j - orders[i].time] + orders[i].value;
- track[i][j] = j - orders[i].time;
- chosen[i][j] = true;
- }
- }
- }
- // 找出最大收益值
- int max_value = 0, best_time = 0;
- for (int j = 0; j <= X; j++) {
- if (dp[j] > max_value) {
- max_value = dp[j];
- best_time = j;
- }
- }
- // 回溯找出選擇的訂單編號
- vector<int> selected_orders;
- int j = best_time;
- for (int i = N - 1; i >= 0; i--) {
- if (chosen[i][j]) {
- selected_orders.push_back(orders[i].id);
- j = track[i][j];
- }
- }
- // 按訂單編號排序並輸出
- sort(selected_orders.begin(), selected_orders.end());
- for (size_t i = 0; i < selected_orders.size(); i++) {
- if (i > 0) cout << " ";
- cout << selected_orders[i];
- }
- cout << endl;
- cout << max_value << endl;
- return 0;
- }
這個問題類似於「0/1 背包問題」，我們可以使用**動態規劃（Dynamic Programming, DP）**來解決。
解題思路
定義狀態：
設 dp[j] 為考慮前 i 個訂單，在時間限制 j 下所能獲得的最大收益。
狀態轉移方程：
若不選擇第 i 筆訂單：dp[j] = dp[i-1][j]
若選擇第 i 筆訂單（前提是 j >= time）：
dp[j] = max(dp[i-1][j], dp[i-1][j-time] + value)
優化空間複雜度：
只使用一維陣列 dp[j]，並從 X 往 0 更新，避免重複計算。
回溯找出選擇的訂單編號：
根據 dp[j] 追蹤哪些訂單被選擇。
-------------------------------------------------------------
解釋程式碼
讀取輸入：
先讀取 N（訂單數量），再讀取 N 筆訂單資料（id, time, value）。
讀取 X（總可用時間）。
使用 DP 陣列 dp[j] 記錄最高收益：
dp[j] 代表在 j 分鐘內所能獲得的最高收益。
使用逆序遍歷 j 來確保每個訂單僅被選擇一次。
使用 track 與 chosen 陣列進行回溯：
chosen[j] 記錄是否選擇了訂單 i。
track[j] 記錄上一個時間點的位置，以便回溯找出最佳解。
輸出結果：
透過 track 回溯找出被選擇的訂單，並按照訂單編號排序後輸出。
最後輸出最高收益值。
時間與空間複雜度
時間複雜度：O(N * X)，因為我們對每個訂單都要遍歷 X。
空間複雜度：O(N * X)，用於 dp、chosen 和 track。
-------------------------------------------------------
測資
測試 00：基本測試
說明：N=5，小明有 X=75 分鐘，剛好能選取多個訂單。
0
5
11 20 35
21 25 45
13 35 50
4 30 50
22 25 35
75
✅ 預期輸出
複製
編輯
4 11 21
130
測試 01：恰好填滿時間
說明：N=4，小明有 X=50 分鐘，剛好能填滿時間。
4
5 10 20
6 20 40
7 30 60
8 40 80
50
預期輸出
6 7
100
測試 02：時間不足
說明：N=3，但小明只有 X=10 分鐘，無法選取任何訂單。
3
1 15 30
2 20 40
3 25 50
10
預期輸出
（空行）
0
測試 03：所有訂單時間超過 X
說明：N=6，所有訂單的花費時間都超過 X=20 分鐘。
6
9 25 50
10 30 60
11 35 70
12 40 80
13 45 90
14 50 100
20
預期輸出
（空行）
0
測試04：大範圍測試
說明：N=8，小明有 X=100 分鐘，應該選擇收益最高的訂單。
8
15 15 30
16 20 50
17 25 60
18 30 70
19 35 80
20 40 90
21 45 100
22 50 110
100
預期輸出
17 19 21
240
這些測資涵蓋 基本情境、極端情境（無法選取、時間剛好填滿）、大範圍數據，可以幫助驗證程式的正確性！ |
