欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Charlie's Change 背包

程序员文章站 2022-07-16 12:11:28
...

Charlie’s Change
原题链接https://vjudge.net/contest/348156#problem/B
Charlie's Change 背包
Charlie's Change 背包

#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
long long num[4];
long long path[10005];
long long used[10005];
long long ans[10005];
long long dp[100005];
long long mv[5]= {1,5,10,25};//硬币的种类
int main()
{
	long long sum;
	while(~scanf("%lld %lld %lld %lld %lld",&sum,&num[0],&num[1],&num[2],&num[3]))//输入数据
	{
		if(sum==0&&num[0]==0&&num[1]==0&&num[2]==0&&num[3]==0)//如果都为0则代表着结束程序
		{
			break;
		}
	//	printf("%lld %lld %lld %lld%lld\n",sum,num[0],num[1],num[2],num[3]);
		memset(path,0,sizeof(path));
		memset(dp,-1,sizeof(dp));
		path[0]=-1;//输出结束条件
		dp[0]=0;
		long long i,j;
		for(i=0; i<4; i++)
		{
			memset(used,0,sizeof(used));//记录当前种类硬币使用的个数
			for(j=mv[i]; j<=sum; j++)
			{
				if(dp[j-mv[i]]+1>dp[j]&&dp[j-mv[i]]>=0&&used[j-mv[i]]<num[i])//判断硬币个数是否增加,上一种情况是否存在,以及硬币个数是否够用
				{
					dp[j]=dp[j-mv[i]]+1;//记录
			    	used[j]=used[j-mv[i]]+1;//记录使用当前硬币的个数
		!!		path[j]=j-mv[i];//记录上一节点;
				}
			}
		}
	//	printf("%lld\n",dp[sum]);
		if(dp[sum]<0)//如果没有情况,输出
		{
			printf("Charlie cannot buy coffee.\n");
			continue;
		}
		memset(ans,0,sizeof(ans));
		while(1)
		{
			if(path[sum]==-1)//结束条件,表示判断到0;
			{
				break;
			}
			ans[sum-path[sum]]++;//当前硬币种类数量加1,由!!处可以得出mv[i]也就是硬币的种类,有公式计算可以得出ans[]中的内容。
			sum=path[sum];//通过节点回溯
		}
		printf("Throw in %lld cents, %lld nickels, %lld dimes, and %lld quarters.\n",ans[mv[0]],ans[mv[1]],ans[mv[2]],ans[mv[3]]);//输出每个种类的个数
	}
	return 0;
}
相关标签: 背包

上一篇: 背包J题 背包

下一篇: Dollars 背包