背包问题

   Author: Gentleman.Hu
   Create Time: 2020-11-08 12:39:42
   Modified by: Gentleman.Hu
   Modified time: 2020-11-08 13:10:13
   Email: [email protected]
   Home: https://crushing.xyz
   Description: 对背包问题的探索与学习

背包问题

https://www.acwing.com/problem/content/2/

问题描述

有N件物品和一个容量是V的背包.每件物品只能使用一次.

有i件物品的体积是Vi,价值是Wi.

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大. 输出最大价值.

输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积.

接下来有N行,每行两个整数Vi,Wi,用空格隔开,分别表示第i件物品的体积和价值.

输出格式 输出一个整数,表示最大价值.

数据范围 0<N,V<=1000 0<Vi,Wi<=1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

8

Soltion

一维动态规划状态转移方程解释