题解

​ 这道题目可以看作是一个经典的 0-1 背包问题，其中每个整数可以视为一个物品，该整数的和可以视为物品的价值，我们的目标是恰好填满一个和为 $m$ 的“背包”，同时使得使用的整数数量最少。

定义 $dp[i][j]$ 表示从前 $i$ 个整数中选取一些整数，其总和恰好为 $j$ 时的最小数量。状态转移方程如下：

问题描述

小红面临一个挑战，他有一系列的整数并且想要挑选出其中的某些数，使得这些数的总和恰好等于一个给定的目标值。每个数只能用一次，小红的目标是找到所需整数数量最少的解决方案。如果没有办法达成目标，他需要得到的回答是“No solution”。

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别代表小红有的整数数量和他想要达到的目标和。

第二行包含 $n$ 个正整数，每两个数之间用一个空格隔开，代表小红拥有的整数序列。

输出格式

输出一个整数，表示达成目标和所需的最少整数数量；如果无法达成目标和，则输出“No solution”。

样例输入1

5 5
1 3 2 1 1

样例输出1

2

样例输入2

5 4
2 3 3 3 3

样例输出2

No solution

评测数据与规模

• 保证 $1 \leq n \leq 1000$，$1 \leq m \leq 100000$。
• 每个整数都小于等于 $100000$。