A70688. 简单背包问题
编程题
入门
知识点
题目描述
有一个背包能装的重量 maxw (正整数，0 \le maxw \le 20000)，同时有 n 件物品(1 \le n \le 100)，每件物品有一个重量 w_i (正整数)和一个价值 p_i (正整数)。要求从这 n 件物品中任取若干件装入背包内，使背包的物品价值最大。
输入格式
第 1 行：背包最大载重 maxw，物品总数 n ；
第 2 行到第 n+1 行：每个物品的重量和价值；
输出格式
一个数字即背包内物品最大价值；
输入输出样例
输入 #1
10 3 4 5 3 4 6 9
输出 #1
14
说明/提示
## 思路
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。