对于给定的分数量,如果所有管子保持64个但不需要填充,则最小化硬币管的数量

Question

编辑:如果有人可以提供一个解释的递归答案(链接会做)与着名的硬币更改问题这将有助于很多

---

对于给定的分数量,如果所有管可以容纳64个硬币,则最小化硬币管的数量.

每个管只能装一种硬币.

每个管不需要完全填充.

---

例如,对于美国硬币,金额为0.01美元,0.05美元,0.10美元,0.25美元,0.50美元和1.00美元

单管6英寸硬币可以做6美分,

25美分可以是一个25c硬币的管子或一个带有5个5c硬币的管子.

65美分将作为13个5c硬币完成,因为65个1c硬币将需要使用2个管.

---

我正在尝试编写一个Minecraft插件,我对这个算法有很多困难.

Answer 1

像这样的东西：

a[0] = 100; //cents
a[1] = 50; a[2] = 25; a[3] = 10; a[4] = 5; a[5] = 1;

cnt[6]; //array to store how much coins of type i you use;


void rec(sum_left, p /* position in a array */) {
   if ( p == 5 ) {
      cnt[5] = sum_left;
      //count how many tubes are used by cnt array, update current answer if neccessary;
      return;
   }
   for ( int i = 0; i <= sum_left/a[p]; i++ )
      //take i coins of type a[p]
      rec(sum_left - i*a[i], p+1);
}

int main() {
   rec(sum, 0);
}