首页 > 代码库 > [九度OJ]货币问题，解题报告

[九度OJ]货币问题，解题报告

2024-07-03 04:43:37   224人阅读

题目

题目描述：
已知有面值为1元，2元，5元，10元，20元，50元，100元的货币若干（可认为无穷多），需支付价格为x的物品，并需要恰好支付，即没有找零产生。
求，至少需要几张货币才能完成支付。
如，若支付价格为12元的物品，最少需要一张10元和一张2元，即两张货币就可完成支付。
输入：
输入包含多组测试数据，每组仅包含一个整数p（1<=p<=100000000），为需支付的物品价格。
输出：
对于每组输入数据，输出仅一个整数，代表最少需要的货币张数。
样例输入：
10
11
13
样例输出：
1
2
3

思路一

这道题目我第一反应是动态规划，假设dp[i]为价格为x的物品所需要的货币张数，则dp[i] = Min{dp[i - 1] + 1, dp[i - 2] + 1, dp[i - 5] + 1, dp[i - 10] + 1, dp[i - 20] + 1, dp[i - 50] + 1, dp[i - 100] + 1}。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VALUE 0x7FFFFFFF

int min_value(int *dp, int loc) {
	int one, two, five, ten, twenty, fifty, hundred, min;

	one = loc - 1 >= 0 ? dp[loc - 1] + 1 : MAX_VALUE;
	two = loc - 2 >= 0 ? dp[loc - 2] + 1 : MAX_VALUE;
	five = loc - 5 >= 0 ? dp[loc - 5] + 1 : MAX_VALUE;
	ten = loc - 10 >= 0 ? dp[loc - 10] + 1 : MAX_VALUE;
	twenty = loc - 20 >= 0 ? dp[loc - 20] + 1 : MAX_VALUE;
	fifty = loc - 50 >= 0 ? dp[loc - 50] + 1 : MAX_VALUE;
	hundred = loc - 100 >= 0 ? dp[loc - 100] + 1 : MAX_VALUE;

	min = one;

	if (min > two) {
		min = two;
	}

	if (min > five) {
		min = five;
	}

	if (min > ten) {
		min = ten;
	}

	if (min > twenty) {
		min = twenty;
	}

	if (min > fifty) {
		min = fifty;
	}

	if (min > hundred) {
		min = hundred;
	}

	return min;
}

int calculate_num(int p) {
	int *dp = (int *)malloc(sizeof(int) * (p + 1));
	dp[0] = 0;

	int i;
	for (i = 1; i <= p; i ++) {
		dp[i] = min_value(dp, i);
	}

	return dp[p];
}

int main(void) {
	int p, res;

	while (scanf("%d", &p) != EOF) {
		res = calculate_num(p);
		printf("%d\n", res);	
	}

	return 0;
}

但是九度OJ判定的结果是：




思路2

出于节省内存考虑，肯定是不能用动态规划了，我们可以模拟一下正常人解决这个问题的思路。假设价格为254,
  1. 首先从100判断，取2张100，还剩下54
  2. 然后从50判断，取1张50，剩下4块
  3. 然后从20、10、5考虑均不符合
  4. 然后考虑2，取两张2，搞定

因为我们可以遍历数组int money[7] = {1, 2, 5, 10, 20, 50, 100}, 从最大到最小去判断

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int calculate_num(int p) {
	int money[7] = {1, 2, 5, 10, 20, 50, 100};
	int i, tmp, num = 0;

	for (i = 6; i >= 0; i --) {
		if (p >= money[i]) {
			tmp = p / money[i];
			p = p % (tmp * money[i]);
			num += tmp;
		}
	}

	return num;
}


int main(void) {
	int p, res;

	while (scanf("%d", &p) != EOF) {
		res = calculate_num(p);
		printf("%d\n", res);	
	}

	return 0;
}


联系
我们