=== 注意: 本题除了求最多能装的价值，还求恰好装满背包时的最大价值。====

描述
你有一个背包，最多能容纳的体积是 $V$。现在有 $n$ 个物品，第 $i$ 个物品的体积为 $v_i$,价值为 $w_i$。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数 $n$ 和 $V$ ，表示物品个数和背包体积。接下来 $n$ 行，每行两个数 $v_i$ 和 $w_i$，表示第 $i$ 个物品的体积和价值。

$1≤n,V,v_i,w_i ≤ 1000$

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1
输入：

3 5
2 10
4 5
1 4

输出：

14
9

说明：
装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。

示例2

输入：

3 8
12 6
11 8
6 8

输出：

8
0

说明：
装第三个物品时总价值最大但是不满，装满背包无解。
备注：
要求 $O(nV)$ 的时间复杂度，$O(V)$ 空间复杂度

题解

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int w[N], v[N], f[N], g[N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < n ;i++) {
        cin >> v[i] >> w[i];        
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    memset(g, -1e6, sizeof g);
    g[0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = m; j >= v[i]; j--) {
            g[j] = max(g[j], g[j-v[i]] + w[i]);
        }
    }        
    cout << f[m] << endl;
    if(g[m] < 0) cout << 0 << endl;
    else cout << g[m] << endl;
    return 0;
}