给定n种物品和一个背包,物品i的重量是Wi,价值是vi,被包容量是C,应该如何选择装入被包的物品,使得装入背包中物品的总价值最大?对于每种物品i,只有两种选择,装入或者不装入.

输入:第一行两个正整数n(物品数)和C(容量)

第二行n个正整数n,表示物品价值

第三行n个正整数n,表示物品重量

输出:第一行表示总价值

第二行n个数(0/1),0表示物品不装入,1表示装入

例如,

输入:

5 10

6 3 5 4 6

2 2 6 5 4

输出

15

1 1 0 0 1

-Species of a given n items and a backpack, the weight of item i is Wi, the value of vi, was packet capacity is C, should be how to choose a package of items to be loaded, the backpack load in the largest total value of goods? For each item i, there are only two options, loaded or not loaded. Input: the first line of the two positive integer n (the number of items) and C (capacity) of the second line of n positive integer n, that the value of the third line of n positive integer n, that the weight of output: the total value of the first line of the second line, said n number of (0/1), 0 that the items do not load, that load 1 for example, enter: 5,106,354,622 6 5 4 output 15 1 1 0 0 1