请教一道面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道面试题

请教一道面试题# JobHunting - 待字闺中

a*u2010-03-22 07:03

1 楼

You are given some denominations of coins in an array (int denom[])and
infinite supply of all of them. Given an amount (int amount), find the
minimum number of coins required to get the exact amount
for example, 面值数组 denom = {7, 5, 3}, target amount = 32, minimum number
of coins needed is 6 (2x7 + 3x5 + 1x3 = 32)
想到的只有greedy。。。有没有优雅一点的解法？

d*82010-03-22 07:03

2 楼

Greedy有些面值数组算出来是错的，会没有解。
DP可以做，但是就是很慢

number

【在 a*u 的大作中提到】

: You are given some denominations of coins in an array (int denom[])and
: infinite supply of all of them. Given an amount (int amount), find the
: minimum number of coins required to get the exact amount
: for example, 面值数组 denom = {7, 5, 3}, target amount = 32, minimum number
: of coins needed is 6 (2x7 + 3x5 + 1x3 = 32)
: 想到的只有greedy。。。有没有优雅一点的解法？

a*u2010-03-22 07:03

3 楼

恩，DP可以O(CN)解出来。
另外一个想法：保持n个queue for each denomination,用backtrack的方法解? 好处就
是可以跳过不可能的amount，但是还没想清楚具体操作。

y*i2010-03-22 07:03

4 楼

我刚写了一个，不知道有没有什么地方可以优化的，感兴趣的可以看一下，我们可以讨
论一下，也让我学习一下，谢谢了！
// Find minimum number of coins to get the exact amount
int FindCoins(int demon[], int nd, int amount)
{
int* N = new int[nd]; // save the number of each coins
memset(N, 0, nd*sizeof(int));
int n = 0, sum = 0;
while (sum != amount)
{
if (sum < amount) // continue to add current denomination
{
sum += demon[n];
++N[n];
}
else // back-track to subtract current coins
{
while

【在 a*u 的大作中提到】

: 恩，DP可以O(CN)解出来。
: 另外一个想法：保持n个queue for each denomination,用backtrack的方法解? 好处就
: 是可以跳过不可能的amount，但是还没想清楚具体操作。

x*32010-03-22 07:03

5 楼

linear programming, simplex method
assume given array A[1:n], each value is a coin value
need to compute x[1:n], each value is a integer >= 0, equals to the number
of a particular coin
solve this minimization
x[1]+x[2]+...+x[n]
subject to
x >= 0
A*transpose(x) = amount

s*t2010-03-22 07:03

6 楼

interesting!

【在 x******3 的大作中提到】

: linear programming, simplex method
: assume given array A[1:n], each value is a coin value
: need to compute x[1:n], each value is a integer >= 0, equals to the number
: of a particular coin
: solve this minimization
: x[1]+x[2]+...+x[n]
: subject to
: x >= 0
: A*transpose(x) = amount

x*32010-03-22 07:03

7 楼

simplex method 不一定给出整数解
可能还是用DP比较好

【在 s*********t 的大作中提到】

: interesting!

a*u2010-03-22 07:03

8 楼

感兴趣！
明天要去onsite, 回来再拜读

【在 y**i 的大作中提到】

: 我刚写了一个，不知道有没有什么地方可以优化的，感兴趣的可以看一下，我们可以讨
: 论一下，也让我学习一下，谢谢了！
: // Find minimum number of coins to get the exact amount
: int FindCoins(int demon[], int nd, int amount)
: {
: int* N = new int[nd]; // save the number of each coins
: memset(N, 0, nd*sizeof(int));
: int n = 0, sum = 0;
: while (sum != amount)
: {

x*r2010-03-22 07:03

9 楼

c#的解，请帮我看看对不对，谢谢
测试过{3, 5, 7}和32 的时候答案是6
public static void findDenominations(int[] denom, int Value){
int[] DP = new int[Value + 1];
DP[0] = 0;

for (int i = 1; i <= Value ++i){
int min = 9999;
for (int j = 0; j < denom.Length; ++j){
int prev = Value - denom[j];
if (prev > -1 && DP[prev] < min)
min = DP[prev];
}
DP[i] = min + 1;
}
Console.WriteLine(DP[Value]);
}