1047: 01背包问题（初阶）

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：688 Solved：211

Description

有N个物品，每个物品的重量是wi  ,每个物品的价值是vi 。

求解当背包容量为W时，能获得的最大价值，并输出获得最大价值时每种物品是否在背包内



数据范围 0 < n <= 30

重量、价值、背包容量均为正整数

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第一行两个数，N和W，N表示物品的个数，W表示容量限制

接下来N行，每行两个数，分别是wi和vi，分别表示第i个物品的重量和价值

Output

第一行一个数，为最大价值

第二行N个数，依次表示各个物品的是否放在背包里（0表示不放，1表示放），如果有多种方案，取字典序最小的。

Sample Input Copy 

8 13
1 1
2 3
5 5
7 7
2 2
1 5
6 6
5 9

Sample Output Copy 

22
0 1 1 0 0 1 0 1

HINT

需要考虑剪枝

Source/Category