小米大礼包（二零一八年九月二十日）在线笔试

题目描述

小米之家实际上是一家面向成年人的糖果店铺，店内陈列着大量价格亲民、实用且趣味性强的商品。随着中秋节的临近，小米之家计划为米粉们准备一些固定金额的礼品套装。针对特定金额，需判断是否能够通过不同种类的商品（每种商品在礼包中最多仅出现一次）组合而成。请运用你的智慧协助米家的小伙伴们完成这一任务。

输入

输入N（N为正整数，且N≤200）
输入N个价格p（均为正整数，且p<10000），各价格之间用单个空格分隔
输入金额M（M为正整数，且M≤100000）

输出

若能够组合出该金额，则输出 1
否则输出 0

样例输入

6
99 199 1999 10000 39 1499
10238

样例输入

1

题目解析

关键词：

• 背包问题
• k-sum
• 寻找多