A70700. 环游世界之背包问题
编程题
入门
知识点
题目描述
张老师准备环游世界，出发之前要做的最重要的事情，当然是整理自己的背包啦。张老师有一个容积为m的背包 ，有n个物品作为放入背包的待选物品 ，每样东西都有自己的价值Wi，和体积Vi ，第i个物品有Ni个 （Ni=0时表示有无限多个），请你编程帮助张老师计算，他的背包能够存入的最大价值是多少？
30\%数据满足 1 <= m,n <=1000
100\%数据满足 1 <=m,n <= 10000
输入格式
第1行有2个整数N,M，表示物品的种类和背包的容积；
第2-N+1行，每行有3个整数Vi，Wi，Pi，分别表示每个物品的体积，价值，个数。（体积<=5000,价值<=5000,个数<=1000）
输出格式
一个整数，表示能够存入背包的最大价值。
输入输出样例
输入 #1
5 50 1 1 50 2 4 3 48 49 1 1 51 1 3 3 3
输出 #1
106
说明/提示
## 思路
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。