(多重背包+记录路径)Charlie's Change (poj 1787)

http://poj.org/problem?id=1787

描述

Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motorests. Charlie hates change. That is basically the setup of your next task.

Your program will be given numbers and types of coins Charlie has and the coffee price. The coffee vending machines accept coins of values 1, 5, 10, and 25 cents. The program should output which coins Charlie has to use paying the coffee so that he uses as many coins as possible. Because Charlie really does not want any change back he wants to pay the price exactly.

输入

Each line of the input contains five integer numbers separated by a single space describing one situation to solve. The first integer on the line P, 1 <= P <= 10 000, is the coffee price in cents. Next four integers, C1, C2, C3, C4, 0 <= Ci <= 10 000, are the numbers of cents, nickels (5 cents), dimes (10 cents), and quarters (25 cents) in Charlie‘s valet. The last line of the input contains five zeros and no output should be generated for it.输出For each situation, your program should output one line containing the string "Throw in T1 cents, T2 nickels, T3 dimes, and T4 quarters.", where T1, T2, T3, T4 are the numbers of coins of appropriate values Charlie should use to pay the coffee while using as many coins as possible. In the case Charlie does not possess enough change to pay the price of the coffee exactly, your program should output "Charlie cannot buy coffee.".

样例输入

12 5 3 1 2
16 0 0 0 1
0 0 0 0 0

样例输出

Throw in 2 cents, 2 nickels, 0 dimes, and 0 quarters.
Charlie cannot buy coffee.

对于这题说法不一, 有人说是多重背包, 有人说是完全背包, 反正我是当多重背包看了, 但是看看人家写的完全背包还是不难理解的, 挺巧妙的

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;

#define met(a,b) (memset(a,b,sizeof(a)))
#define N 11000
#define INF 0x3f3f3f3f

int pre[N], v[5]={0,1,5,10,25}, dp[N];
int used[N];

/**

dp[i]   代表组成i元时需要的最多的硬币
used[i] 代表第i种硬币用了几次(感觉这点很好,能将多重背包转化为完全背包)
pre[j]  记录的是j从哪个状态转化过来的

*/

int main()
{
    int p, num[5]={0};

    while(scanf("%d%d%d%d%d", &p, &num[1], &num[2], &num[3], &num[4]), p+num[1]+num[2]+num[3]+num[4])
    {
        int i, j, ans[110]={0};

        met(dp, -1);
        met(pre, -1);
        dp[0] = 0;
        for(i=1; i<=4; i++)
        {
            memset(used, 0, sizeof(used));
            for(j=v[i]; j<=p; j++)
            {
                if(dp[j-v[i]]+1>dp[j] && dp[j-v[i]]>=0 && used[j-v[i]]<num[i])
                {
                     dp[j] = dp[j-v[i]]+1;
                     used[j] = used[j-v[i]]+1;
                     pre[j] = j-v[i];
                }
            }
        }

        if(dp[p]<0)
           printf("Charlie cannot buy coffee.\n");
        else
        {
            met(ans, 0);
            i = p;
            while(1)
            {
                if(pre[i]==-1) break;
                ans[i-pre[i]]++;
                i = pre[i];
            }
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[v[1]], ans[v[2]], ans[v[3]], ans[v[4]]);
        }

    }
    return 0;
}

(多重背包+记录路径)Charlie's Change (poj 1787)

时间: 05-28

(多重背包+记录路径)Charlie's Change (poj 1787)的相关文章

Charlie&#39;s Change POJ - 1787 (完全背包+记录路径)

完全背包输出路径:对于每一次更新记录一下路径:注意钱币个数: dp[i][0]代表在空间为i时需要多少枚钱币 dp[i][1]用来记录路径 cheek[j]用来记录在j时用了多少i枚钱币 思路在代码中: #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define mem(a,b) memset(a,b,sizeof

poj1787Charlie&#39;s Change(多重背包+记录路径+好题)

Charlie's Change Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 3720   Accepted: 1125 Description Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motore

POJ - 1787 (多重背包还原路径|| 完全背包)

POJ  1787  Charlie's Change Description Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motorests. Charlie hates change. That is basically the setup of your next task

poj 1787 背包+记录路径

http://poj.org/problem?id=1787 Charlie's Change Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 4512   Accepted: 1425 Description Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at co

POJ 1293 Duty Free Shop(背包记录路径)

Description Pedro travelled to Europe to take part in the International Olympiad in Informatics and is coming back home. Since all his friends asked him to bring them some gift, he bought two big bags of chocolates (one of Mindt and one of Lilka). Ea

poj1417 带权并查集 + 背包 + 记录路径

True Liars Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 2713   Accepted: 868 Description After having drifted about in a small boat for a couple of days, Akira Crusoe Maeda was finally cast ashore on a foggy island. Though he was exha

UVA 624(01背包记录路径)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=565 记录路径可以用一个二维数组,记录改变时的量.然后从后往前可以推得所有的值. #include <iostream> #include <string> #include <cstring> #include <cstdlib> #incl

UVA624(01背包记录路径)

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=565 01背包打印路径. #include <cstdio> #include <cstring> using namespace std; const int MAXN=10005; int n,W; int w[30]; int dp[MAXN]; in

POJ 1787 Charlie&amp;#39;s Change

多重背包 可行性+路径记录 题意是说你要用很多其它的零钱去买咖啡.最后输出你分别要用的 1,5 ,10 .25 的钱的数量. 多重背包二进制分解.然后记录下 这个状态.最后逆向推就可以. #include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #