#O1035. 完全背包
完全背包
题目描述
有 种物品,第 种重 、价值 ,每种物品可以取任意多件,背包容量为 ,求最大总价值。
题目类型
动态规划、完全背包
输入格式
第一行两个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
一行一个整数,表示最大总价值。
样例 #1
样例输入 #1
2 5
1 3
2 5
样例输出 #1
10
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 物品种数 | |
| 背包容量 | |
| 重量 | |
| 价值 |
有 n 种物品,第 i 种重 wi、价值 vi,每种物品可以取任意多件,背包容量为 W,求最大总价值。
动态规划、完全背包
第一行两个整数 n,W。
第二行 n 个整数 wi。
第三行 n 个整数 vi。
一行一个整数,表示最大总价值。
2 5
1 3
2 5
10
| 数据范围 | 说明 |
|---|---|
| 1≤n≤500 | 物品种数 |
| 0≤W≤5×104 | 背包容量 |
| 1≤wi≤109 | 重量 |
| 1≤vi≤106 | 价值 |