#O1034. 0/1 背包
0/1 背包
题目描述
有 件物品,第 件重 、价值 ,背包容量为 。每件物品最多取一次,求能取得的最大总价值。
题目类型
动态规划、0/1 背包
输入格式
第一行两个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
一行一个整数,表示最大总价值。
样例 #1
样例输入 #1
4 5
1 2 3 4
2 4 4 5
样例输出 #1
8
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 物品数 | |
| 背包容量 | |
| 重量,超过 的物品直接舍弃 | |
| 价值 |
有 n 件物品,第 i 件重 wi、价值 vi,背包容量为 W。每件物品最多取一次,求能取得的最大总价值。
动态规划、0/1 背包
第一行两个整数 n,W。
第二行 n 个整数 wi。
第三行 n 个整数 vi。
一行一个整数,表示最大总价值。
4 5
1 2 3 4
2 4 4 5
8
| 数据范围 | 说明 |
|---|---|
| 1≤n≤500 | 物品数 |
| 0≤W≤105 | 背包容量 |
| 1≤wi≤109 | 重量,超过 W 的物品直接舍弃 |
| 1≤vi≤106 | 价值 |