<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
西瓜的表弟小西瓜生病住院了，西瓜想去买一个水果篮子探望他。水果店里面有很多种类的水果篮子，价格相同，但是水果的搭配各不相同。西瓜突然想到了一个问题，现在水果店里面有这么N种水果，第i个水果单价是Pi元，西瓜手上有M元钱（钱不一定要花完，但也不能什么水果都没有），一共有几种搭配水果篮子的方法呢。
</blockquote>
 
<h2 id="input">Input</h2>
<blockquote>
题目包含多组输入，EOF结束，数据最多不超过100组，对于每组数据，包含两行，第一行是两个整数N，M，表示水果的总数和西瓜手里的钱数。第二行包含N个整数，表示每种水果的单价。 
1 &lt;= N &lt;= 10, 1 &lt;= M &lt;= 200, 1 &lt;= Pi &lt;= M
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
对于每组输入，输出一行，表示有多少种搭配水果篮子的方法。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
2 10 
3 4 
9 100 
5 6 9 13 4 5 3 9 8
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
7 
1954041
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
<a href="/post/Algorithm/Package_Problem.html">&gt;背包问题 - 01背包问题&lt;</a>
背包问题的计数问题
<code>dp[i][j]</code> 表示前i件水果在钱数为j时的可行的选择种类数目
则有 <code>d[i][j] = (d[i-1][j] + 1) + d[i][j-price[i]]</code>
分别代表买和不买这个物品
初始状态为<code>dp[0][0] = 0</code>(什么都买不了)
压缩成一维数组 <code>d[j] += ((j - price[i] &gt;= 0) ? (d[j - price[i]] + 1) : 0);</code>
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;stack&gt;
using namespace std;

#define REP(n) for(int o=0;o&lt;n;o++)

int N,M;//N水果数 M钱数
const int maxn = 15;
const int maxm = 205;
long long d[maxm];
int price[maxn];

bool Do() {
 if(scanf(&#34;%d%d&#34;,&amp;N,&amp;M) == EOF)
 return false;
 REP(N)
 scanf(&#34;%d&#34;,&amp;price[o + 1]);
 
 memset(d,0,sizeof(d));
 for(int i = 1;i &lt;= N;i++)
 for(int j = 1;j &lt;= M;j++)
 d[j] += ((j - price[i] &gt;= 0) ? (d[j - price[i]] + 1) : 0);

 printf(&#34;%lld\n&#34;,d[M]);
 return true;
}

int main() {
 while(Do());
 return 0;
}
</pre>

791.水果篮子