Problem A: 算法实验 8-1 回溯算法-01背包问题

Problem A: 算法实验 8-1 回溯算法-01背包问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 906  Solved: 692
[Submit] [Status] [Web Board] [Creator:]

Description

有 n 个重量分别为{w1， w2，…， wn}的物品，它们的价值分别为{v1， v2，…，vn}，给定一个容量为 W 的背包。
设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且满足重量限制具有最大的价值。

Input

第1行输入n;
第2行输入背包容量W；
后面n行依次输入每个物品的重量和价值；

Output

第1行输出01背包问题的最优价值；
第2行输出一个向量，表示物品的装载情况；

Sample Input Copy 

4
6
5 4
3 4
2 3
1 1

Sample Output Copy 

8
0 1 1 1
[Submit][Status]