问题 1846 --部分背包问题(bag) [1*+]

1846: 部分背包问题(bag) [1*+]

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

部分背包问题(bag)
【题目描述】 有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元,重Wi磅,(1≤i≤n),此处Vi和Wi都是整数。他希望带走的东西越值钱越好,但他的 背包中最多只能装下W磅的东西(W为整数),小偷可带走某个物品的一部分(只带走其中的几磅也为整�?,小偷应该带走哪几件东西,每件东西的重量是多少?

【输入】输入第一行为N W (N<=10000 W<=30000),后面N行描述每个物品,每行两个数,即为Vi与Wi

【输出】输出第一行为大的最大价值(取整),后面依次描述物品i应偷多少(如果没偷,则不输出,输出对应的i为升序)。

输入

输出

提示

来源

[提交][状态]