m*********a
发帖数: 47 | 1 输入：
一个整数，代表需要的金钱总额(in cents)
一个整数数组，代表可用的各种硬币的面值(in cents, e.g.: 1, 5, 10, 25)
输出：
一个整数，代表可能的组合的个数
一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
。。。。。 | m***n
发帖数: 2154 | 2 一个简单的递归算法
public static int numberofways(int [] denom, int start, int amount, String
prefix) {
int total=0;
if(start>denom.length-1) return 0;
if(amount==0) {
System.out.println(prefix+" "+ amount +":"+ denom[start]);
return 1;
}
//if(denom[start]==amount) return 1;
if(start==denom.length-1) {
System.out.println(prefix+" "+ amount +":"+ denom[start]);
return 1;
};
for(int i=0;i
total+=numberofways(denom,start+1,amount-i*denom[start],prefix+"
"+ i+ ":"+denom[start]);
}
return total;
} | m***n
发帖数: 2154 | 3 这样算的话，你dp[0-25]还要手动初始化。。 | l*****a
发帖数: 14598 | 4 写的太难懂了
String
【在 m***n 的大作中提到】
: 一个简单的递归算法
: public static int numberofways(int [] denom, int start, int amount, String
: prefix) {
:
: int total=0;
: if(start>denom.length-1) return 0;
: if(amount==0) {
: System.out.println(prefix+" "+ amount +":"+ denom[start]);
: return 1;
: }
| m***n
发帖数: 2154 | 5 算法就是把硬币排序， 从大的排起。。
最多包含 x= amount/denom[k] 个 k硬币， 类似于一个BFS 的N-ary tree 搜索了
【在 l*****a 的大作中提到】
: 写的太难懂了
:
: String
| l*****a
发帖数: 14598 | 6 void GetCombination(int array[],int size,int target,int start,int* counter,
vector&vec)
{
if(target==0) { *counter++; return; }
for(int i=start;i
{
if(array[i]>target) break;
vec.push_back(array[i]);
GetCombination(array,size,target-array[i],i,counter,vec);
vec.pop_back();
}
}
【在 m***n 的大作中提到】
: 算法就是把硬币排序， 从大的排起。。
: 最多包含 x= amount/denom[k] 个 k硬币， 类似于一个BFS 的N-ary tree 搜索了
| l*****a
发帖数: 14598 | 7 计数的时候打印就可以了
另外初始数组是有序的[1,2,5,10]否则当然不对 | l*****a
发帖数: 14598 | 8 它要求记录所有结果？还是一个就成？
需要所有的就改成记录所有的。。。 | l*****a
发帖数: 14598 | 9 我从小的开始，如果不使用了之后就永远不会再用，所以不会重复
比方说，use 1,2,3,4 to get 4
1,1,1,1
1,1,2,
1,3,
2,2
4
but 1,2,1 can't appear | p*****2
发帖数: 21240 | 10
不好意思。没仔细看C＋＋程序。这个程序写的很巧妙。赞一个。
【在 l*****a 的大作中提到】
: 我从小的开始，如果不使用了之后就永远不会再用，所以不会重复
: 比方说，use 1,2,3,4 to get 4
: 1,1,1,1
: 1,1,2,
: 1,3,
: 2,2
: 4
: but 1,2,1 can't appear
| | | t*********7
发帖数: 255 | 11 递归啊,从大到小逐级转换啊,到最后全部为1了就结束了 | l*****a
发帖数: 14598 | 12 我用vector放一次的结果
用vector>放所有的结果。。
【在 p*****2 的大作中提到】
:
: 不好意思。没仔细看C＋＋程序。这个程序写的很巧妙。赞一个。
| p*****2
发帖数: 21240 | 13
恩。算法很好。用hashmap是不是产生结果更快些？
【在 l*****a 的大作中提到】
: 我用vector放一次的结果
: 用vector>放所有的结果。。
| k****e
发帖数: 297 | 14 来个通俗版本
默认硬币从大到小排列：
void GetCombinationSet(const int *anCoin, int *anCount, int x, int i)
{
if(x>anCoin[i])
{
if (i
{
int *anCountNew = new int[g_nCoinType];
CopyArray(anCount, anCountNew);
GetCombinationSet(anCoin, anCountNew, x, i+1);
}
anCount[i]++;
GetCombinationSet(anCoin, anCount, x-anCoin[i], i);
}
else if (x == anCoin[i])
{
if (i
{
int *anCountNew = new int[g_nCoinType];
CopyArray(anCount, anCountNew);
GetCombinationSet(anCoin, anCountNew, x, i+1);
}
anCount[i]++;
OutputCount(anCount);
delete[] anCount;
}
else
{
i++;
if (i < g_nCoinType)
{
GetCombinationSet(anCoin, anCount, x, i);
}
}
}
【在 m*********a 的大作中提到】
: 输入：
: 一个整数，代表需要的金钱总额(in cents)
: 一个整数数组，代表可用的各种硬币的面值(in cents, e.g.: 1, 5, 10, 25)
: 输出：
: 一个整数，代表可能的组合的个数
: 一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
: 一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
: 一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
: 。。。。。
| h********w
发帖数: 221 | 15 牛！
【在 l*****a 的大作中提到】
: void GetCombination(int array[],int size,int target,int start,int* counter,
: vector&vec)
: {
: if(target==0) { *counter++; return; }
: for(int i=start;i: {
: if(array[i]>target) break;
: vec.push_back(array[i]);
: GetCombination(array,size,target-array[i],i,counter,vec);
: vec.pop_back();
| R******9
发帖数: 267 | 16 #include
#include
using namespace std;
void printCoins(const vector&coins, int index, vectorsoFar, int
val)
{
if(val<0)
return;
if(val==0){
for(int i=soFar.size()-1; i>=0; i--)
cout<
cout<
}
for(int i=index; i>=0; i--){
soFar.push_back(coins[i]);
printCoins(coins,i,soFar,val-coins[i]);
soFar.pop_back();
}
}
void printCoins(const vector&coins, int val){
vector soFar;
printCoins(coins,coins.size()-1, soFar,val);
}
【在 m*********a 的大作中提到】
: 输入：
: 一个整数，代表需要的金钱总额(in cents)
: 一个整数数组，代表可用的各种硬币的面值(in cents, e.g.: 1, 5, 10, 25)
: 输出：
: 一个整数，代表可能的组合的个数
: 一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
: 一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
: 一个整数数组，代表一种组合(e.g.: 2 1 1 5, 代表2个1分，1个5分）
: 。。。。。
|
|
