#3635. KKT基本算法背包问题

KKT基本算法背包问题

题目描述

小明就要去春游了。妈妈给他买了很多好吃的。小明想把这些吃的都放进他的书包,但他很快发现,妈妈买的东西实在太多了,他必须放弃一些,但又希望能带尽可能多的好吃的。 已知小明的书包最多可以装入总重量为 ss 的物品,同时也知道小明妈妈给他买的每样东西的重量。请从这些好吃的中选出若干装入小明的书包中,使得装入物品的总重量正好为 ss。找到任意一组解输出即可。

输入格式

第1行包含两个正整数 nnss,分别代表有 nn 件物品和书包的最大承重 ss; 第2行包含 nn 个正整数,代表每件物品的重量 WiW_i。同行的两个数字之间用一个空格隔开。

输出格式

一行包含有若干用一个空格隔开的正整数,代表被放入书包的若干物品各自的重量。若无可行解,则输出 No Answer!

样例 #1

样例输入 #1

8 14
1 3 2 5 9 4 7 6

样例输出 #1

1 3 4 6

样例 #2

样例输入 #2

3 12
2 8 5

样例输出 #2

No Answer!

提示

数据范围:

  • 1n1001 \le n \le 100
  • 1s100001 \le s \le 10000
  • 1Wi10001 \le W_i \le 1000