/*
题意：
T组测试数据，每组给出 n 和 m，n代表商品数目，m是所拥有的钱，然后给出 n 个商品价格，
求出可以买的最多商品种类数，以及对应的方案数
思路：
对于此题，第一个想法便是以价格作为费用，件数1作为价值，01背包即可求出花费 m 所能获得的商品的最大件数 dp[m]。
不过，又要求其方案数，自己试着敲了一下代码WA，后来参考了此篇博客AC掉了。。。
需要建立一个数组 select[j]，存储花费 j 元钱买 dp[j] 件商品的方案数。
1） dp[j-arr[i]] + 1 > dp[j]:
则select[j]是由select[j-arr[i]]决定的，因为当前只不过在花费 j-arr[i] 元钱所能购买的商品中又加入了第i个商品，使之花费为j，故方案数还是select[j]。
注意：如果此时 0 == select[j-arr[i]]， 则select[j] = 1，因为花费 j 元钱只选第 i 个商品，也是一种方案。
2）dp[j-arr[i]] + 1 == dp[j]:
如果此时在花费j元时，（选择第i件商品后的商品件数==不选择第i件商品后的商品件数），
那么 select[j] = select[j-arr[i]] + select[j] (即选/不选第i件商品的两种情况下的方案数的总和)
注意：如果此时 0 == select[j-arr[i]]，则 select[j] = 1 + select[j]，解释同上。。
3）dp[j-arr[i]] + 1 < dp[j]:
可见方案数是由花费 j 元钱，不选第 i 件商品情况下决定的， 故：select[j] = select[j]
*/
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstdio>
4 #include <cstring>
5 using namespace std;
6 const int MAX_N = 35, MAX_M = 505;
7 int n, m, arr[MAX_N], dp[MAX_M], select[MAX_M];
8
9 void Solve() {
10 memset(dp, 0, sizeof(dp));
11 memset(select, 0, sizeof(select));
12 for (int i = 1; i <= n; ++i) {
13 for (int j = m; j >= arr[i]; --j) {
14 if (dp[j - arr[i]] + 1 > dp[j]) {
15 dp[j] = dp[j - arr[i]] + 1;
16 if (select[j - arr[i]]) select[j] = select[j - arr[i]];
17 else select[j] = 1;
18 }
19 else {
20 if (dp[j - arr[i]] + 1 == dp[j]) {
21 if (select[j - arr[i]]) select[j] += select[j - arr[i]];
22 else select[j] += 1;
23 }
24 }
25 }
26 }
27 if (select[m]) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.
", select[m], dp[m]);
28 else printf("Sorry, you can't buy anything.
");
29 }
30
31 int main()
32 {
33 //freopen("input.txt", "r", stdin);
34 //freopen("output.txt", "w", stdout);
35 int T;
36 scanf("%d", &T);
37 while (T--) {
38 scanf("%d %d", &n, &m);
39 for (int i = 1; i <= n; ++i) {
40 scanf("%d", &arr[i]);
41 }
42 Solve();
43 }
44 return 0;
45 }