动态规划解决0/1背包问题
输入格式:
第1行是M和n,表示背包容量为M且有n件物品;
第2行是这n件物品的重量w
i;
第3行是各物品的价值p
i ,背包容量和物品重量都为整数。
输出格式:
第1行是所选物品的价值之和,以及重量之和;
第2行是各物品装入背包的量,即x i值。
输入样例1:
6 3
2 3 4
1 2 5
输出样例1:
6 6
1 0 1
输入样例2:
100 10
13 2 10 50 1 28 37 32 30 46
12 23 37 45 19 11 25 9 14 18
输出样例2:
149 100
0 1 1 1 1 0 1 0 0 0