问题 3615 --0-1 背包问题(动态规划)

3615: 0-1 背包问题(动态规划)

时间限制: 1 Sec  内存限制: 128 MB
提交: 166  解决: 55
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

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

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

输入

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

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

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

第四行输入背包容量c。


输出

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

第二行输出最大价值。

样例输入

3
3 4 5
4 5 6
10

样例输出

011
11

提示

来源

[提交][状态]