【题目描述】

商店正在出售蒜头君最喜欢的系列玩具，在接下来的 " 周中，每周会出售其中的一款，同一款玩具不会重复出现。由于是蒜头君最喜欢的系列，他希望尽可能多地购买这些玩具，但是同一款玩具蒜头君只会购买一个。同时，蒜头君的预算只有元，因此他无法将每一款都纳入囊中。此外，蒜头君不能连续两周都购买玩具，否则他会陷入愧疚。现在蒜头君想知道，他最多可以买多少款不同的玩具呢?

【输入格式】

输入共2行:

第一行两个正整数几和 m，中间用一个空格隔开;

第二行共几个正整数，第i个正整数表示第:周出售的玩具的价格

【输出格式】

输出文件只有一行，包含一个整数，表示蒜头君最多能买多少款不同的玩具，

【数据范围】

对于 30%的数据，n< 10，m< 100;

对于 60%的数据，n< 100，m< 1000;

对于 100% 的数据，n< 1000，m< 50000，单个玩具的价格< 1000。

------------------------------

【题目分析】

很显然，这个题目是一个背包问题，我们设置 dp 数组为 dp|ij]，表示第i周预算为j的最多可以买多少款不同的玩具。

通过转移方程 dp[i][j]= max(dp[i-1][j],dp[i-2][j-a[i]]+ 1);和 dp[i][j|= dp[i- 1][j]; 进行转移即可。