#O1034. 0/1 背包

0/1 背包

题目描述

有 nn 件物品,第 ii 件重 wiw_i、价值 viv_i,背包容量为 WW。每件物品最多取一次,求能取得的最大总价值。

题目类型

动态规划、0/1 背包

输入格式

第一行两个整数 n,Wn, W。

第二行 nn 个整数 wiw_i。

第三行 nn 个整数 viv_i。

输出格式

一行一个整数,表示最大总价值。

样例 #1

样例输入 #1

4 5
1 2 3 4
2 4 4 5

样例输出 #1

8

数据规模与约定

数据范围 说明
1≤n≤5001 \le n \le 500 物品数
0≤W≤1050 \le W \le 10^5 背包容量
1≤wi≤1091 \le w_i \le 10^9 重量,超过 WW 的物品直接舍弃
1≤vi≤1061 \le v_i \le 10^6 价值