Nowcoder girl 2019: 第三题 背包问题

题目链接🔗：背包问题

题意简述

这道题不穿衣服就上来了，不仅是个裸01背包问题，而且名字也叫“背包问题”，仿佛出题人在拼命提示改一改01背包问题就可以了。【从这题开始，命题人就开始在标题里提示做法了（除了泡面233）】

不会01背包问题的同学可以戳 这里 有金牌大佬的视频讲解。

解题思路 （没错，就是DP）

我们先回忆一下01背包问题与这题的区别：

• 01背包问题：求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。【体积 有上限，价值 越大越好】
• 牛妹背包问题：总体积不小于 的前提下，物品的总价值最小是多少。【这题的总价 可以看作有上限 (看似用来限制 的体积下限，实际上是在干涉 )，而体积 越多越好】

(看见这道题的时候一度怀疑出题人直接把模板题复制了过来，但是赛后一查发现并没有这样的模板题。可能因为世界上除了哆啦A梦，谁也没有这样的玄学背包………）
 
我们依样画葫芦地对比一下01背包问题和牛妹背包问题中 （有些同学习惯用 ）所代表的意思：

• 01背包问题：在前 个物品中选，体积为 的这些可选方案中，价值最大值为多少。
• 牛妹背包问题：在前 个物品中选，价值为 的这些可选方案中，体积最大值为多少。
   

然后我们就发现，只要把01背包问题中的体积和价值的变量名换一下就好了。
但是不要忘了，最后求的是总价的最小值，要把 从小到大遍历，第一个超过 的，就是我们想找的答案。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=210,M=40010;
int n,V;
int v[N],w[N];
int f[M];//f[i][j]表示在前i个物品里选，价值是j的情况下的最大体积

int main(){
    cin>>n>>V;
    int sum;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
        sum+=w[i];//价值的上限需要我们自己累加一下
    }

    //DP过程与01背包相同，就是换了个变量名
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=w[i];j--){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }

    //最后，第一个满足“体积不小于V”的价值，就是我们要找的价值
    for(int i=1;i<=sum;i++){
        if(f[i]>=V){
            cout<<i<<endl;
            break;
        }
    }

    return 0;
}