PAT 解题报告 1068. Find More Coins (30)

1068. Find More Coins题目描述:

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

题目就是给定一系列的硬币值, 然后给定一个目标value, 从所有硬币中找出几个, 使得这几个硬币的和正好等于这个value, 而且这个硬币序列应该是满足硬币值字典序的最小序列.

1068. Find More Coins算法分析:

这个属于典型的背包问题. 要是知道0/1背包问题就不难解决了. 用动态规划(dp)做, 假设F(N, M)表示不超过面值M, 而且从前面N个硬币中挑选硬币值能得到的最大硬币面值总和, 那我们可以得到如下递归公式:

F(N, M) = max{ F(N – 1, M), F(N – 1, M – V(N)) + V(N) }, V(N)表示第N个硬币的面值

那么最后要是F(N, M)  == M, 那么就说明我们可以找到这样一组硬币, 使得他们的面值总和恰好等于M. 剩下的问题是如何记录路径, 也就是怎么记录挑选出哪些硬币? 我们可以开另一个空间叫做isIncluded(N, M), isIncluded(N, M)为真, 则表示从前面N个硬币中选出一组得到最多的不超过M的币值总和里面包括了第N个硬币. 那么如果我们需要找到完整路径, 我们就可以从N, M出发, 一直回溯到最后一个硬币. 这里其实也隐含要求了给原始的硬币降序排序(降序排序的另一个作用就是保证字典序), 下面是可以AC的代码:

#include <cstdio>
#include <cmath>
#include <algorithm>

const int ncoins = 10005;
const int nmonay = 105;

bool cmp(const int &a, const int &b) {
    return a > b;
}

int main() {
    int dp[ncoins][nmonay];
    int  coins[ncoins];
    bool isIncluded[nmonay][ncoins];

    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &coins[i]);
    }
    std::sort(coins + 1, coins + n + 1, cmp);

    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            isIncluded[i][j] = false;

    for(int i = 0; i <= m; ++i) dp[0][i] = 0;
    for(int i = 0; i <= n; ++i) dp[i][0] = 0;

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if( j < coins[i] || dp[i - 1][j] >  coins[i] + dp[i - 1][j - coins[i]] ) {
                dp[i][j] = dp[i - 1][j];
            }
            else {
                dp[i][j] = dp[i - 1][j - coins[i]] + coins[i];
                isIncluded[j][i] = true;
            }
        }

    if(dp[n][m] != m) {
        printf("No Solution\n");
        return 0;
    }

    bool flag = true;
    for(int i = n; i >= 1 && m > 0; --i) {
        if(isIncluded[m][i]) {
            if(flag) {
                printf("%d", coins[i]);
                flag = false;
            }
            else
                printf(" %d", coins[i]);
            m -= coins[i];
        }
    }
    printf("\n");
    return 0;
}

1068. Find More Coins注意点:

先给所有的硬币降序排序用于保证字典序.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on October 14, 2013