洛谷P1164小A点菜

这也是一道01背包的题

用的方法比较的巧妙。这个动态规划相当于反过来做的，自己理解就知道了。代码很短

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,m;

     cin>>n>>m;

     int f[],money[];

     f[]=;//这个方便计数

     for (int i=;i<=n;i++) cin>>money[i];

     for (int i=;i<=n;i++)

         for (int j=m;j>=money[i];j--)//为什么到money[i]呢是因为不可能小于money[i],money[i]是只选这个的情况

           f[j]+=f[j-money[i]];

     cout<<f[m]<<endl;

 }