3814. Maximum Capacity Within Budget

📘 題目敘述

給定兩個長度相同的整數陣列：

costs[i]：第 i 個設備的花費
capacity[i]：第 i 個設備所提供的容量

以及一個整數 budget，代表可使用的總預算。

你可以選擇：

不選任何設備
只選一個設備
或選兩個不同的設備

前提是所選設備的總花費 小於 budget。

請回傳在預算限制內，可以達到的最大總容量。

條件限制

1 ≤ costs.length == capacity.length ≤ 100
0 ≤ costs[i], capacity[i], budget ≤ 10^5

🧠 解題思路（但最後TLE）

我的想法是直接把所有「可能的選擇情況」都列出來比較：

這題最多只能選 兩個設備，因此所有情況其實只有三種：

不選任何設備（容量為 0）
只選一個設備
選兩個不同的設備

因為陣列長度不大，我選擇用 暴力枚舉 的方式，直接檢查每一種可能，並在符合預算的情況下更新最大容量。

所有變數

n：設備的數量（costs.size()）
ncap：目前找到的最大總容量
i, j：用來枚舉設備索引的迴圈變數

🪜 主要流程步驟

第一部分：只選一個設備

我先考慮「只選一個設備」的情況：

逐一檢查每個設備 i
若 costs[i] < budget
- 表示單獨購買這個設備是可行的
在所有可行的設備中
- 持續更新最大的 capacity[i]

這一步是為了處理「最佳解只需要一個設備」的情況。

第二部分：選兩個不同的設備

接著考慮「選兩個設備」的情況：

使用兩層迴圈枚舉所有 (i, j) 且 i < j
對每一組設備：
- 檢查 costs[i] + costs[j] < budget
- 若符合預算限制
  - 計算總容量 capacity[i] + capacity[j]
  - 與目前的 ncap 比較，更新最大值

這樣可以確保所有「兩設備組合」都被完整檢查過。

為什麼這樣做是可行的？

題目限制最多只能選兩個設備
資料規模允許 O(n^2) 的解法
暴力枚舉能完整涵蓋所有可能情況
邏輯直覺、好驗證、不容易寫錯

💻 程式碼實作

class Solution {
public:
    int maxCapacity(vector<int>& costs, vector<int>& capacity, int budget) {
        int ncap = 0;
        int n = costs.size();

        // 只選一個設備
        for (int i = 0; i < n; i++) {
            if (costs[i] < budget && capacity[i] > ncap) {
                ncap = capacity[i];
            }
        }

        // 選兩個不同的設備
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (costs[i] + costs[j] < budget) {
                    if (capacity[i] + capacity[j] > ncap) {
                        ncap = capacity[i] + capacity[j];
                    }
                }
            }
        }

        return ncap;
    }
};

🔗 題目連結

https://leetcode.com/problems/maximum-capacity-within-budget/