首页 > 代码库 > POJ 2581 Exact Change Only（dp）
POJ 2581 Exact Change Only（dp）
Language: Exact Change Only
Description Boudreaux reached over and shook awake Thibodeaux, who had dozed off somewhere in New Mexico. "Where we at?" Thibodeaux groggily yawned. "Not in Vegas, I gua-ran-tee, but could you get my knapsack?" Boudreaux asked, gesturing to the worn, leather backpack in the back seat of their cherry red Ford Miata. "Why, is there a problem?" "Just hand me my knapsack, problem or not." Thibodeaux complied, glancing up as Boudreaux slowed the car to a stop in a line of vehicles approaching a toll booth. "$1.65 -- Exact change only," Thibodeaux read the yellow sign on the front of a small wooden building occupied by a lone toll booth operator. "I have to get $1.65 in exact change?" Thibodeaux asked, digging through the knapsack, "all I have are ten quarters, four dimes, and three pennies. I don‘t have any nickels . . ." "Just give me five of the quarters and the four dimes," Boudreaux replied, holding out his hand. "Oh yeah," Thibodeaux said, handing over the coins, "that does add up to $1.65. I wish there were an easy way to figure out if you have an exact monetary amount, given a set of coins." "Hmmm," Boudreaux shrugged, "sounds like a good programming problem." Input Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. A single data set has 1 component: Start line - A single line: A B C D E where: A: (0.01 <= A <= 5.00) is a decimal number (to two decimal places) of a monetary amount. B: (0 <= B <= 100) is an integer number of quarters (one quarter = $0.25). C: (0 <= C <= 100) is an integer number of dimes (one dime = $0.10). D: (0 <= D <= 100) is an integer number of nickels (one nickel = $0.05). E: (0 <= E <= 100) is an integer number of pennies (one penny = $0.01). Output For each data set, there will be exactly one line of output. If there exists one or more subsets of the given coins whose values add up to the given monetary amount exactly, the output will be a single line in the form: A B C D where A is the number of quarters, B is the number of dimes, C is the number of nickels, and D is the number of pennies, for the subset with the fewest number of coins. Otherwise, the output will be a single line with the statement: NO EXACT CHANGE Sample Input 0.45 2 1 1 4 0.75 3 7 1 75 Sample Output NO EXACT CHANGE 3 0 0 0 Source South Central USA 2003 |
就是把钱放大100倍后看组合成all，种钱最少需要几张钱？
dp+记录路径，值得一提的是这个题也可以4个for循环过，但是还是感觉dp高大上一点吧
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1000
int num[5],dp[N],pre[N],all;
int op[5]={25,10,5,1};
int ans[N];
int main()
{
int i,j;
double x;
while(~scanf("%lf",&x))
{
all=(int)(x*100);
for(i=0;i<4;i++)
scanf("%d",&num[i]);
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=0;i<4;i++)
{
if(op[i]*num[i]>=all)
{
for(int v=op[i];v<=all;v++)
if(dp[v-op[i]]&&(dp[v]==0||dp[v]>dp[v-op[i]]+1))
{
dp[v]=dp[v-op[i]]+1;
pre[v]=v-op[i];
}
}
else
{
int t=num[i];
while(t--)
{
for(int v=all;v>=op[i];v--)
if(dp[v-op[i]]&&(dp[v]==0||dp[v]>dp[v-op[i]]+1))
{
dp[v]=dp[v-op[i]]+1;
pre[v]=v-op[i];
}
}
}
}
if(!dp[all])
{
printf("NO EXACT CHANGE\n");
continue;
}
memset(ans,0,sizeof(dp));
i=all;
while(i)
{
ans[i-pre[i]]++;
i=pre[i];
}
printf("%d %d %d %d\n",ans[25],ans[10],ans[5],ans[1]);
}
return 0;
}
POJ 2581 Exact Change Only（dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。