首页 > ACM题库 > HDU-杭电 > hdu 2126 Buy the souvenirs-动态规划-[解题报告]C++
2013
12-29

hdu 2126 Buy the souvenirs-动态规划-[解题报告]C++

Buy the souvenirs

问题描述 :

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).

输入:

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.

输出:

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.

样例输入:

2
4 7
1 2 3 4

4 0
1 2 3 4

样例输出:

You have 2 selection(s) to buy with 3 kind(s) of souvenirs.
Sorry, you can't buy anything.

http://acm.hdu.edu.cn/showproblem.php?pid=2126

题意:给你n种物品以及每种物品的价格,m的钱,问你在满足买最多种物品的前提下,有多少种不同的够买方案

解法1:

首先献上我的比较挫的方法,也是大众化的方法,dp[i][j][k]表示前i种物品,买了j个,花了小于等于k的钱的时候的方案数

因为是小于等于k,所以初始化的时候要注意哦。

那么转移的时候第i种物品取或者不取

dp[i][j][k]+=dp[i-1][j-1][k-p[i]];
 dp[i][j][k]+=dp[i-1][j][k];
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[35][35][510];
int p[35];
int main()
{
	int t,m,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&p[i]);
		memset(dp,0,sizeof(dp));
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=m;j++)
			   dp[i][0][j]=1;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				for(int k=m;k>=0;k--)
				{
					if(k>=p[i])   dp[i][j][k]+=dp[i-1][j-1][k-p[i]];
				   	 dp[i][j][k]+=dp[i-1][j][k];
				//	printf("i=%d j=%d k=%d %d\n",i,j,k,dp[i][j][k]);
				}
			}
		}
		int ops=-1,kinds=-1;
		for(int i=n;i>=1;i--)
		{
			for(int j=i;j>=1;j--)
			{
				for(int k=m;k>=0;k--)
				{
					if(dp[i][j][k])
					{
						//printf("%d %d %d\n",i,j,k);
						kinds=j;
						ops=dp[i][j][k];
						break;
					}
				}
				if(kinds!=-1) break;
			}
			if(kinds!=-1) break;
		}
		if(ops!=-1)
		{
			printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",ops,kinds);
		}
		else printf("Sorry, you can't buy anything.\n");
	}
	return 0;
}

解法二:直接变成rank2了!!!

其实也很简单,可以这样设计状态开一个dp[30][500][2]的数组,dp[i][j][0]就表示前i个物品,花了 <= j 的钱,最多可以买到的纪念品数量,dp[i][j][1]就表示买到最多纪念品前提下的方案数了,转移的时候就按照关键字来转移,

先判断能否增加所买的纪念品的种类数,

再判断种类数相同的时候的情况

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[31][501][2];
int v[31];
int main()
{
	int t,m,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&v[i]);
		memset(dp,0,sizeof(dp));
		for(int i=0;i<=m;i++) dp[0][i][1]=1;
		for(int i=0;i<=n;i++) dp[i][0][1]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<v[i];j++) dp[i][j][0]=dp[i-1][j][0],dp[i][j][1]=dp[i-1][j][1];
			for(int j=v[i];j<=m;j++)
			{
				if(dp[i-1][j-v[i]][0]+1>dp[i-1][j][0])
				{
					dp[i][j][0]=dp[i-1][j-v[i]][0]+1;
					dp[i][j][1]=dp[i-1][j-v[i]][1];
				}
				else if(dp[i-1][j-v[i]][0]+1==dp[i-1][j][0])
				{
					dp[i][j][0]=dp[i-1][j][0];
					dp[i][j][1]=dp[i-1][j][1]+dp[i-1][j-v[i]][1];
				}
				else 
				{
					dp[i][j][0]=dp[i-1][j][0];
					dp[i][j][1]=dp[i-1][j][1];
				}
			}
		}
		if(dp[n][m][0]) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[n][m][1],dp[n][m][0]);
		else printf("Sorry, you can't buy anything.\n");
	}
	return 0;
}

解法三:rank1

优化是永无止境的~    突然发现只有最后一层的状态有用,那就用滚动数组试试吧

结果,直接跑到了rank1

精益求精,截图留念一下


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[501][2], v[31];
int main()
{
	int t,m,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&v[i]);
		memset(dp,0,sizeof(dp));
		for(int i=0;i<=m;i++) dp[i][1]=1;
		for(int i=1;i<=n;i++)
		{
			dp[0][1]=1;
			for(int j=m;j>=v[i];j--)
			{
				if(dp[j-v[i]][0]+1>dp[j][0])
				{
					dp[j][0]=dp[j-v[i]][0]+1;
					dp[j][1]=dp[j-v[i]][1];
				}
				else if(dp[j-v[i]][0]+1==dp[j][0])
				{
					dp[j][1]=dp[j][1]+dp[j-v[i]][1];
				}
			}
		}
		if(dp[m][0]) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[m][1],dp[m][0]);
		else printf("Sorry, you can't buy anything.\n");
	}
	return 0;
}

还有些人竟然可以用0kb的内存,- -!,难道是纯数学方法?

解题转自:http://blog.csdn.net/crazy_ac/article/details/7869411


  1. [email protected]