完全背包模板

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

链接：登录—专业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;
}