Problem1465--0-1背包问题

1465: 0-1背包问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,背包的容量为C。如何选择装入背包的物品,可以使得装入背包中物品的总价值最大?

Input

每组输入包括三行,
第一行包括物品个数n,以及背包容量C。
第二、三行包括两个一维数组,分别为每一种物品的价值和重量。

Output

输出包括两行,第一行为背包的最大总价值,第二行为所选取的物品。
例如:最大总价值=15,物品选取策略为11001。

Sample Input Copy

5 10
6 3 5 4 6
2 2 6 5 4

Sample Output Copy

15
11001

Source/Category