hdu 2126 Buy the souvenirs
共 4376字，需浏览 9分钟
· 2021-10-01
Buy the souvenirs
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4129 Accepted Submission(s): 1617
Problem Description
When the winter holiday comes, a lot of people will have a trip. Generally, there are a lot of souvenirs to sell, and sometimes the travelers will buy some ones with pleasure. Not only can they give the souvenirs to their friends and families as gifts, but also can the souvenirs leave them good recollections. All in all, the prices of souvenirs are not very dear, and the souvenirs are also very lovable and interesting. But the money the people have is under the control. They can’t buy a lot, but only a few. So after they admire all the souvenirs, they decide to buy some ones, and they have many combinations to select, but there are no two ones with the same kind in any combination. Now there is a blank written by the names and prices of the souvenirs, as a top coder all around the world, you should calculate how many selections you have, and any selection owns the most kinds of different souvenirs. For instance:
And you have only 7 RMB, this time you can select any combination with 3 kinds of souvenirs at most, so the selections of 3 kinds of souvenirs are ABC (6), ABD (7). But if you have 8 RMB, the selections with the most kinds of souvenirs are ABC (6), ABD (7), ACD (8), and if you have 10 RMB, there is only one selection with the most kinds of souvenirs to you: ABCD (10).
Input
For the first line, there is a T means the number cases, then T cases follow.
In each case, in the first line there are two integer n and m, n is the number of the souvenirs and m is the money you have. The second line contains n integers; each integer describes a kind of souvenir.
All the numbers and results are in the range of 32-signed integer, and 0<=m<=500, 0<n<=30, t<=500, and the prices are all positive integers. There is a blank line between two cases.
Output
If you can buy some souvenirs, you should print the result with the same formation as “You have S selection(s) to buy with K kind(s) of souvenirs”, where the K means the most kinds of souvenirs you can buy, and S means the numbers of the combinations you can buy with the K kinds of souvenirs combination. But sometimes you can buy nothing, so you must print the result “Sorry, you can't buy anything.”
Sample Input
2
4 7
1 2 3 4
4 0
1 2 3 4
Sample Output
You have 2 selection(s) to buy with 3 kind(s) of souvenirs.
Sorry, you can't buy anything.
买的纪念品
内存限制:32768/32768 K (Java/Others)
总提交数:4129已接受提交数:1617
问题描述
当寒假来临的时候，很多人都会去旅行。一般来说，有很多纪念品出售，有时游客会买一些愉快的。他们不仅可以把纪念品作为礼物送给他们的朋友和家人，也可以留下美好的回忆。总之，纪念品的价格不是很贵，而且纪念品也非常可爱和有趣。但是人民的钱是在控制之下的。他们不能买很多，只能买少数。所以在他们欣赏完所有的纪念品后，他们决定买一些，他们有很多组合来选择，但没有两个在任何组合中是相同的。现在有一个空白写着纪念品的名字和价格，作为一个世界顶尖的程序员，你应该计算你有多少选择，任何选择拥有最多种类的不同的纪念品。例如:
这次和你只有7元,您可以选择任何结合三种纪念品,所以选择3种纪念品ABC (6), ABD(7)。但是如果你有8元,最多的选择类型的纪念品是ABC (6), ABD(7)、ACD(8),如果你有10元,这里只有一种纪念品可供选择:ABCD(10)。
输入
对于第一行，T表示数种情况，然后T种情况。
在每一种情况下，第一行都有两个整数n和m, n是纪念品的数量，m是你拥有的钱。第二行包含n个整数;每个整数表示一种纪念品。
所有的数字和结果都在32符号整数范围内，0<=m<=500, 0两种情况之间有一行空白。
输出
如果你可以买些纪念品,你应该打印同样的结果形成“你与K S (S)选择购买的纪念品”,其中K意味着大多数种类的纪念品可以买,和S意味着组合的数字你可以买纪念品的K类的组合。但有时你什么也买不到，所以你必须打印“对不起，你不能买任何东西。”
Sample Input
2
4 7
1 2 3 4
4 0
1 2 3 4
Sample Output
You have 2 selection(s) to buy with 3 kind(s) of souvenirs.
Sorry, you can't buy anything.
解题思路：
当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。
代码：
#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
return (a>b?a:b);
}
int main()
{
int t,n,m,p[35];
int i,j,dp[505][2];
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&p[i]);
memset(dp,0,sizeof(dp));
for(i=0;i<m;i++)
dp[i][1]=1;
for(i=0;i<n;i++)
{
for(j=m;j>=p[i];j--)
{
if(dp[j][0]==dp[j-p[i]][0]+1)
dp[j][1]=dp[j-p[i]][1]+dp[j][1];
else if(dp[j][0]<dp[j-p[i]][0]+1)
dp[j][1]=dp[j-p[i]][1];
dp[j][0]=max(dp[j][0],dp[j-p[i]][0]+1);//状态转移方程
}
}
if(!dp[m][0])
printf("Sorry, you can't buy anything.\n");
else
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[m][1],dp[m][0]);
}
}
return 0;
}