|
|---|
|
|
|
|
|
|
a*u
发帖数: 97 | 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*******8
发帖数: 785 | 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*u
发帖数: 97 | 3 恩，DP可以O(CN)解出来。
另外一个想法：保持n个queue for each denomination,用backtrack的方法解? 好处就
是可以跳过不可能的amount，但是还没想清楚具体操作。 | y**i
发帖数: 1112 | 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******3
发帖数: 245 | 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*********t
发帖数: 1663 | 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******3
发帖数: 245 | 7 simplex method 不一定给出整数解
可能还是用DP比较好
【在 s*********t 的大作中提到】
: interesting!
| a*u
发帖数: 97 | 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****r
发帖数: 99 | 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]);
} |
|
|
|
|
|
|
|
