---
# System prepended metadata

title: 小明買魚

---

>author: Utin

## Question
媽媽叫小明去買魚，他怕小明被當盤子，所以他叫小明在預算之內，要盡可能買到最多熱量的魚，請幫小明算出他買魚可以買到最多的總熱量是多少

### Input
第一行有一個整數 N，代表市場上 N 條魚可以選擇
第二行有 N 個整數，分別代表每條魚的價錢
第三行有 N 個整數，分別代表每條魚的熱量
第四行有個整數 L，代表小明的預算

### Output
輸出小明買到的魚的總熱量

### Constraint
1 <= N <= 20

### Sample Input
```=
6
20 15 35 29 58 37
8 4 7 9 3 6
123
```

### Sample Output
```=
30

```

## 作法
在遞迴裡面塞入迴圈

## 常見問題
- scanf 記得取址
- 注意遞迴裡面 for 迴圈的初始值，這題是要算組合而非排列

## 解法
```c=
#include <stdio.h>

int n, price[20], heat[20], limit, ans = 0;
void count(int index, int sum_w, int sum_v);

int main() {

    // input
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &price[i]);
    for (int i = 0; i < n; i++) scanf("%d", &heat[i]);
    scanf("%d", &limit);

    // count
    for (int i = 0; i < n; i++)
        if (price[i] <= limit) count(i, 0, 0);
    
    // output
    printf("%d\n", ans);
}

void count(int index, int sum_w, int sum_v) {

    // 加總
    sum_w += price[index];
    sum_v += heat[index];

    // 把最大值存起來
    if (ans < sum_v) ans = sum_v;

    // 這是組合不是排列，從index+1開始往後找就好
    for (int i = index + 1; i < n; i++)
        if (sum_w + price[i] <= limit) count(i, sum_w, sum_v);
}
```
