Einführung

Du hast einen Freund, der dich immer wieder um Kredite bittet und du wirst es leid. Heute kam er wieder für einen Kredit. Anstatt sein Angebot abzulehnen, haben Sie eine großartige Idee: Trollen Sie Ihren Freund, indem Sie ihm so viele Münzen / Scheine wie möglich geben.

Herausforderung

Sie nehmen als Eingabe: den Geldbetrag, für den Ihr Freund einen Kredit haben möchte, und den Betrag der Münzen / Scheine, die Sie haben. Für diese Herausforderung sind die möglichen Nennwerte 20,00 USD, 10,00 USD, 5,00 USD, 2,00 USD, 1,00 USD, 0,25 USD, 0,10 USD, 0,05 USD und 0,01 USD. Ein Beispiel für eine Eingabe ist, 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2]wenn Ihr Freund 5,67 US-Dollar möchte und Sie 5 20 US-Dollar-Scheine, 3 10 US-Dollar-Scheine usw. haben. Ihre Ausgabe ist die Menge an Münzen / Scheinen, die Ihrem Freund so viel Metall / Papier / Kunststoff wie möglich gibt.

Wenn es nicht möglich ist, Ihrem Freund den genauen Geldbetrag zu geben, den er möchte, geben Sie ihm den nächstmöglichen Geldbetrag, den Sie bezahlen können, der über dem liegt, was er möchte. Zum Beispiel, wenn Ihr Freund 0,07 € möchte, Sie aber nur haben[0, 0, 0, 0, 0, 2, 4, 2, 0] , geben Sie ihm 2 0,05 USD Münzen (nicht 1 0,10 USD, weil dies ihm nicht so viele Münzen wie möglich geben würde!).

Wenn dein Freund mehr Geld haben möchte als du, gib ihm dein ganzes Geld (und bete, dass du nichts kaufen musst).

Testfälle

Input:  6.54, [9, 8, 7, 6, 5, 4, 3, 2, 4]
Output: [0, 0, 0, 1, 4, 1, 2, 1, 4]

Input:  2, [0, 1, 0, 0, 0, 0, 0, 0, 0]
Output: [0, 1, 0, 0, 0, 0, 0, 0, 0]

Input:  9999, [0, 0, 0, 0, 0, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 1]

Input:  0, [99, 99, 99, 99, 99, 99, 99, 99, 99]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Das ist Code-Golf, also gewinnt der kürzeste Code.

Sauber , 167 Bytes

import StdEnv
@n l#m=[p\\p<-[[if(y==u)(x-1)x\\x<-l&y<-[0..]]\\u<-[0..]&v<-l|v>0]|sum[a*b\\a<-[2000,1000,500,200,100,25,10,5,1]&b<-p]>=toInt(n*100.0)]
|m>[]= @n(hd m)=l

Definiert die Funktion @, Einnahme Realund[Int] .

Probieren Sie es online!

JavaScript, 213 Bytes

x=>y=>(F=(x,y,z,u=9)=>u--?[...Array(y[0]+1)].map((_,i)=>F(x-i*[1,5,10,25,100,200,500,1e3,2e3][u],y.slice(1),[...z,i],u))&&G:x>0||G.push([z,x-1/eval(z.join`+1+`)]),F(x*100,y,G=[]).sort((a,b)=>b[1]-a[1])[0]||[y])[0]

Es ist ziemlich langsam und kostet Speicher, also nur kleine Fälle versuchen

Kotlin , 298 Bytes

{t,c->with(c.fold(listOf(listOf<Int>())){o,x->o.flatMap{a->(0..x).map{a+it}}}.groupBy{it.zip(C).map{(a,b)->a*b}.sum()}.mapValues{(_,b)->b.maxBy{it.sum()}!!}.toSortedMap().asSequence()){firstOrNull{it.key==t}?:firstOrNull{it.key>t}?:last()}.value}
val C=listOf(20.0,10.0,5.0,2.0,1.0,0.25,.1,.05,.01)

Verschönert

        { t, c ->
            with(c.fold(listOf(listOf<Int>())) { o, x ->
                o.flatMap { a -> (0..x).map { a + it } } /* Get all of the options. */
            }.groupBy { it.zip(C).map { (a, b) -> a * b }.sum() }
                .mapValues { (_,b)->b.maxBy { it.sum() }!! }
                .toSortedMap().asSequence()) {
                firstOrNull { it.key == t } ?:
                        firstOrNull { it.key > t } ?:
                        last()
            }.value
        }
val C = listOf(20.0, 10.0, 5.0, 2.0, 1.0, 0.25, .1, .05, .01)

Prüfung

val calc: (target: Double, coins: List<Int>) -> List<Int> =
{t,c->with(c.fold(listOf(listOf<Int>())){o,x->o.flatMap{a->(0..x).map{a+it}}}.groupBy{it.zip(C).map{(a,b)->a*b}.sum()}.mapValues{(_,b)->b.maxBy{it.sum()}!!}.toSortedMap().asSequence()){firstOrNull{it.key==t}?:firstOrNull{it.key>t}?:last()}.value}
val C=listOf(20.0,10.0,5.0,2.0,1.0,0.25,.1,.05,.01)

data class Test(val target: Double, val input: List<Int>, val output: List<Int>)

val tests = listOf(
        Test(2.0, listOf(0, 1, 0, 0, 0, 0, 0, 0, 0), listOf(0, 1, 0, 0, 0, 0, 0, 0, 0)),
        Test(9999.0, listOf(0, 0, 0, 0, 0, 0, 0, 0, 1), listOf(0, 0, 0, 0, 0, 0, 0, 0, 1)),
        Test(6.54, listOf(9, 8, 7, 6, 5, 4, 3, 2, 4), listOf(0, 0, 0, 1, 4, 1, 2, 1, 4)),
        Test(0.0, listOf(99, 99, 99, 99, 99, 99, 99, 99, 99), listOf(0, 0, 0, 0, 0, 0, 0, 0, 0))
)

fun main(args: Array<String>) {
    for (t in tests) {
        if (t.output != calc(t.target, t.input)) {
            throw AssertionError()
        } else {
            println("Passed")
        }
    }
}

Beispiel 4 verursacht OutOfMemory, aber die anderen 3 funktionieren gut.