背包问题 01背包/完全背包/多重背包/分组背包/单调队列优多重背包/二维费用背包

小明的背包1

题目描述

小明有一个容量为VVV的背包。

这天他去商场购物，商场一共有NNN件物品，第iii件物品的体积为wiw_iwi​，价值为viv_ivi​。

小明想知道在购买的物品总体积不超过VVV的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 1 行包含两个正整数N,VN, VN,V，表示商场物品的数量和小明的背包容量。

第2∼N+12 \sim N+12∼N+1行包含 2 个正整数w,vw, vw,v，表示物品的体积和价值。

1≤N≤102, 1≤V≤103, 1≤wi,vi≤1031 \leq N \leq 10^2,\ 1 \leq V \leq 10^3,\ 1 \leq w_i, v_i \leq 10^31≤N≤102,1≤V≤103,1≤wi​,vi​≤103。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入：

5 20 1 6 2 5 3 8 5 15 3 3

输出：

37

#include<iostream>usingnamespacestd;constintN=105,M=1010;usingll=longlong;ll dp[N][M];intmain(){intn,V;cin>>n>>V;for(inti=1;i<=n;i++){ll w,v;cin>>w>>v;for(intj=0;j<=V;j++){//如果装得下当前物体if(j>=w){dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);}//如果装不下else{dp[i][j]=dp[i-1][j];}}}cout<<dp[n][V]<<endl;return0;}