你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为v_ivi ,价值为w_iwi。

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

输入描述：

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

1 \le n,V,v_i,w_i \le 10001≤n,V,vi,wi≤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 <vector>
#include <algorithm>
#include <sstream>
#include <stack>
#include <queue>
#include <unordered_map>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
    int n, v;
    while (cin >> n && cin >> v) { // 注意 while 处理多个 case
        vector<int>vin(n, 0);
        vector<int>win(n, 0);
        for (int i = 0; i < n; i++) {
            cin >> vin[i];
            cin >> win[i];
        }
        int res1 = 0;
        int res2 = 0;
        // dp[i][j]代表将前i个物品装入体积为j的背包时的最大价值
        //vector<vector<int>>dp(n+1, vector<int>(v+1, -1000001));
        //dp[0][0] = 0;
        vector<int>dp(v+1, -1000001);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = v; j >= vin[i-1]; j--) {
                if (j >= vin[i-1]) {
                    dp[j] = max(dp[j], dp[j-vin[i-1]] + win[i-1]);
                } else {
                    dp[j] = dp[j];
                }
                res1 = max(res1, dp[j]);
            }
        }
        cout <<res1 << endl;
        if (dp[v] < 0) {
            res2 = 0;
        } else {
            res2 = dp[v];
        }
        cout << res2 << endl;
    }
}
// 64 位输出请用 printf("%lld")