题目描述

给定n种物品和一个背包，物品i的重量是W_i，其价值为V_i，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？

在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。

输入格式

第一行输入物品的个数n。

第二行输入物品的重量序列w。(中间有空格）

第三行输入物品的价值序列v。（中间有空格）

第四行输入背包容量c。

输出格式

第一行输出装入背包的物品。（用0和1表示，中间无空格）

第二行输出最大价值。

样例

样例 1

输入 # 1

样例

样例 1

输入 # 1

3
3 4 5
4 5 6
10

输出 # 1

011
11

来源

0-1 背包问题（动态规划）