部分背包问题(bag)
【题目描述】
有一个贼在偷窃一家商店时发现有N件物品:第i件物品值Vi元,重Wi磅,(1≤i≤n),此处Vi和Wi都是整数。他希望带走的东西越值钱越好,但他的
背包中最多只能装下W磅的东西(W为整数),小偷可带走某个物品的一部分(只带走其中的几磅也为整�?,小偷应该带走哪几件东西,每件东西的重量是多少?
【输入】输入第一行为N W (N<=10000 W<=30000),后面N行描述每个物品,每行两个数,即为Vi与Wi
【输出】输出第一行为大的最大价值(取整),后面依次描述物品i应偷多少(如果没偷,则不输出,输出对应的i为升序)。