蓝桥杯19682 完全背包

问题描述

有 N 件物品和一个体积为 M 的背包。第 i 个物品的体积为 vi​，价值为 wi​。每件物品可以使用无限次。

请问可以通过什么样的方式选择物品，使得物品总体积不超过 M 的情况下总价值最大，输出这个最大价值即可。

输入格式

第一行输入两个正整数 N,M。(1≤N,M≤1000)

接下来 N 行，每行输入两个整数 vi,wi。(0≤vi,wi≤1000)

输出格式

输出一个整数，表示符合题目要求的最大价值。

样例输入

4 5
1 2
2 4
3 4
4 5

样例输出

10

说明

你可以选择 1 个第一个物品和 2 个第二个物品。

 

 

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e3+10;
int n, m;
int v[N], w[N];  
int dp[N];  //dp[j]表示背包容量为j时的最大价值int main()
{cin>>n>>m;for(int i=1; i<=n; ++i) cin>>v[i]>>w[i];for(int i=1; i<=n; ++i)  //遍历每个物品{//内层循环从v[i]到m正向遍历，这使得同一物品可以被多次选取for(int j=v[i]; j<=m; ++j){//dp[j]：不选当前物品//dp[j - v[i]] + w[i]：选当前物品dp[j] = max(dp[j], dp[j-v[i]] + w[i]);}}cout<<dp[m];return 0;
}