c***2
发帖数: 838 | 1 Given a list of coins such as 25, 10, 5, 1
find the minimum number of coins for a target value such as 95. | c**y
发帖数: 172 | 2 For this problem, greedy algo. works. Always choose the largest coin that is
allowed.
However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy
algo. doesn't work. So we need to use dynamical programming to solve this
problem.
【在 c***2 的大作中提到】
: Given a list of coins such as 25, 10, 5, 1
: find the minimum number of coins for a target value such as 95.
| y***m
发帖数: 7027 | 3 how about this
如果list很大，不要求subarray,就根据coin value 先找出对应的数字组合，从最小组
合开始对list搜索
如果要求subarray 就简单dp..
is
greedy
【在 c**y 的大作中提到】
: For this problem, greedy algo. works. Always choose the largest coin that is
: allowed.
: However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy
: algo. doesn't work. So we need to use dynamical programming to solve this
: problem.
| i**9
发帖数: 351 | 4 //coins sort in reverse order
int coins[]={25,10,5,1};
bool findcoinlist(int coins[],int n,int target){
int i=0;
do{
// greedy to find max coin
for(i=0;i
if(target>=coins[i]){
break;
}
}
cout<
target-=coins[i];
if(target==0){
return true;
}
}while(target>0);
return false;
}
【在 c***2 的大作中提到】
: Given a list of coins such as 25, 10, 5, 1
: find the minimum number of coins for a target value such as 95.
| c***2
发帖数: 838 | 5 RE this.
Eventually we still need to find all possible combinations, then find min
is
greedy
【在 c**y 的大作中提到】
: For this problem, greedy algo. works. Always choose the largest coin that is
: allowed.
: However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy
: algo. doesn't work. So we need to use dynamical programming to solve this
: problem.
|
|
