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

小明的背包1题目描述小明有一个容量为VVV的背包。这天他去商场购物商场一共有NNN件物品第iii件物品的体积为wiw_iwi​价值为viv_ivi​。小明想知道在购买的物品总体积不超过VVV的情况下所能获得的最大价值为多少请你帮他算算。输入描述输入第 1 行包含两个正整数N,VN, VN,V表示商场物品的数量和小明的背包容量。第2∼N12 \sim N12∼N1行包含 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#includeiostreamusingnamespacestd;constintN105,M1010;usinglllonglong;ll dp[N][M];intmain(){intn,V;cinnV;for(inti1;in;i){ll w,v;cinwv;for(intj0;jV;j){//如果装得下当前物体if(jw){dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v);}//如果装不下else{dp[i][j]dp[i-1][j];}}}coutdp[n][V]endl;return0;}