HDU 2126 Buy the souvenirs

题意： 输入t，表示t组样例。然后每组样例输入n,m，n表示物品个数，接着输入n个数。求从这些数中找出和不超过m的最多物品数量Max，以及满足Max个的种类。

分析：dp[i][k][j] 表示前i个物品中，挑选出k个物品的总和为j的数量。那么dp[i][k][j] = dp[i-1][k][j] + dp[i-1][k-1][j-a[i]] 。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn = 505;

int a[33];
int dp[33][maxn];

int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
        }
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int Max = 0;
        for(int i=1; i<=n; i++)
        {
            for(int k=i; k>=1; k--)
            {
                for(int j=a[i]; j<=m; j++)
                {
                    dp[k][j] += dp[k-1][j-a[i]];
                    if(dp[k][j]&&k>Max)
                        Max = k;
                }
            }
        }
        int ans = 0;
        for(int i=0; i<=m; i++)
        {
            ans+=dp[Max][i];
        }
        if(Max==0)
            printf("Sorry, you can't buy anything.
");
        else
            printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.
", ans, Max);
    }

    return 0;
}