# Knapsack Problem

###### tags: `Normal`
>[name=出題者 : 游城棣]

## Problem
有一位愛探險的Dora要出遠門，希望能從想帶的物品中找出最有價值的帶法，你能幫幫她嗎?

### Input
輸入有多⾏：
第一行是有幾樣物品(N)和背包的最大承重量(W)。
接下來是各個物品的重量和價值。

## Output
輸出格式
輸出最大價值

### Examples

輸入範例1
4 12
3 20
4 45
9 70
12 85
輸出範例1
the best solution is: 90

輸入範例2
8 20
12 100
8 60
9 70
3 40
5 60
1 20
2 25
7 48
輸出範例2
the best solution is: 215

### Constraints
0 < N < 100
0 < W < 100000

## Solution
:::spoiler C++

#include <bits/stdc++.h>
using namespace std;
struct item{
    int weigh;
    int value;
} items[100];
int main(){
    int n, w;
    cin >> n >> w;
    int dp[w + 5];
    for (int i = 0; i < n; i++){
        cin >> items[i].weigh >> items[i].value;
    }
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++){
        for (int j = w; j - items[i].weigh >= 0; j--){
            dp[j] = max(dp[j], dp[j - items[i].weigh] + items[i].value);
        }
    }
    cout << "the best solution is: " << dp[w];
}

:::

## Reference
經典背包問題