# Q2. Maximum Capacity Within Budget

**練習日期：** 2026-01-18
**類型：** Weekly Contest 485

## 📘 題目敘述

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

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

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

你可以選擇：
- **不選任何設備**
- **只選一個設備**
- **或選兩個不同的設備**

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

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

### 條件限制
- `1 ≤ costs.length == capacity.length ≤ 100`
- `0 ≤ costs[i], capacity[i], budget ≤ 10^5`

## 🧠 解題思路（但最後TLE）

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

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

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

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

### 所有變數

- `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/contest/weekly-contest-485/problems/maximum-capacity-within-budget/description/