完全背包模板

题目链接：【模板】完全背包

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

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

现在有n种物品，每种物品有任意多个，第i种物品的体积为vi​ ,价值为wi​。

（1）求这个背包至多能装多大价值的物品？

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

输入描述:

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数vi​和wi​，表示第i种物品的体积和价值。

1≤n,V≤1000

输出描述:

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

示例1

输入

2 6
5 10
3 1

输出

10
2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n,V;
    cin >> n >> V;
    vector<int> v(n+1);
    vector<int> w(n+1);
    for (int i=1;i<=n;i++){
        cin >> v[i] >> w[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(V+1,0));
    for (int i=1;i<=n;i++){
        for (int j=0;j<=V;j++){
            dp[i][j]=dp[i-1][j];
            if (j>=v[i])
                dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
                //01背包第二个参数是dp[i-1][j-v[i]]+w[i]
        }
    }
    cout << dp[n][V] << endl;

    vector<vector<int>> dp2(n+1,vector<int>(V+1,-1));
    for (int i=0;i<=n;i++){
        dp2[i][0]=0;
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<=V;j++){
            dp2[i][j]=dp2[i-1][j];
            if (j>=v[i]&&dp2[i][j-v[i]]!=-1)
                dp2[i][j]=max(dp2[i][j],dp2[i][j-v[i]]+w[i]);
            //同样的，01背包这里判断条件是dp2[i-1][j-v[i]]!=-1
            //递推第二个数是dp2[i-1][j-v[i]]+w[i]
        }
    }
    if (dp2[n][V]==-1){
        cout << 0 << endl;
    }
    else {
        cout << dp2[n][V] << endl;
    }
    return 0;
}