题意

• 给定n个物品，每个物品由价值和体积，问装入体积为v的背包的最大价值和恰好装满的最大价值

思路

• 01背包问题，对于每个物品考虑装和不装即可，如果不装\装不下 ，如果装则考虑装进来后的价值 ，对于每一个物品，在装和不装里取最大即可 。

• 注意到，n和val最大都可以取1000，二维数组可以开 ,也可以考虑就地滚动进行优化，那么，每次遍历体积时，为了防止重复更新，需要从v遍历到vol[i](倒序遍历)，同时，由于转移只发生在一层数组中，所以每次更新变为和原值比较最大的

• 初值：对于第一个问题，所有位置初值赋为0即可（可以视作有价值为0体积任意的空气最初填满背包），由于放入每个物品时都会自动从能放入的地方开始到v全部放入，所以每层背包都会保证单增， 即为所求答案。

  对于第二个问题，因为要求恰好填满，所以每一个恰好填满的答案一定是从 开始往后转移的，而不是 开始，所以，除了 赋值为0以外，其他位置都赋一个极小的值（0x3f3f3f3f）,最后，如果 直接输出结果，如果 说明没有可以从0转移过来的路径，输出0。

AC代码

#include<bits/stdc++.h>
using namespace std;
int dp1[101010];
int dp2[101010];
int vol[1010],val[1010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int v,n;
    cin >> n >> v ;
    for(int i=1;i<=n;i++){
        cin >> vol[i] >> val[i] ;
    }
    //v2:就地滚动
    for(int i=1;i<=n;i++){
        for(int j=v;j>=vol[i];j--)
            dp1[j]=max(dp1[j],dp1[j-vol[i]]+val[i]);
    }
    memset(dp2,-0x3f3f3f3f,sizeof(dp2));
    dp2[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=v;j>=vol[i];j--)
            dp2[j]=max(dp2[j],dp2[j-vol[i]]+val[i]);
    }
    cout << dp1[v] << '\n' << max(0,dp2[v]) << '\n';
    return 0;
}