#4170. 01背包
01背包
问题描述
小明就要去春游了,妈妈给他买了很多好吃的。小明想把这些吃的都放进他的书包,但他很快发现,妈妈买的东西实在太多了,他必须放弃一些,但又希望能带尽可能多的好吃的。使用算法解决这个实际问题。
已知小明的书包最多可以装入总重量为 s 的物品,同时也知道小明妈妈给他买的每样东西的重量。请从这些好吃的中选出若干装入小明的书包中,使得装入物品的总重量正好为 s。找到任意一组解输出即可。
输入格式
- 第 1 行包含两个正整数
n(1 ≤ n ≤ 100)和s(1 ≤ s ≤ 10,000),分别代表有n件物品和书包的最大承重s; - 第 2 行包含
n个正整数,代表每件物品的重量W_i(1 ≤ W_i ≤ 1,000)。同行的两个数字之间用一个空格隔开。
输出格式
- 一行包含若干用一个空格隔开的正整数,代表被放入书包的若干物品各自的重量。如果无可行解,则输出
No Answer!。
输入样例
样例 1
8 14
1 3 2 5 9 4 7 6
样例 2
3 12
2 8 5
输出样例
样例 1
1 3 4 6
样例 2
No Answer!