php - texto - Elegir monedas con el menor o ningún cambio dado.

string strip_tags

Question

Estoy haciendo un juego que consiste en denominaciones de monedas de $ 10, $ 5, $ 3 y $ 1. El jugador puede tener 0 o más de cada tipo de moneda en su inventario con un máximo de 15 monedas en total. Estoy tratando de averiguar cómo seleccionar correctamente las monedas para que se dé la menor cantidad de cambio a cambio. Al principio pensé que esto iba a ser fácil de resolver, pero ahora tengo problemas para rodearlo con la cabeza.

Aquí hay dos ejemplos que explican la situación aún más:

Ejemplo 1:

El usuario lleva estas monedas: $ 5, $ 3, $ 3, $ 3, $ 1, $ 1, $ 1, $ 1 y desea comprar un artículo por $ 12. La solución sería pagar con $ 5, $ 3, $ 3, $ 1 y no dar ningún cambio.

Ejemplo 2:

El usuario no tiene ninguna moneda de $ 1 y lleva $ 5, $ 3, $ 3, $ 3, $ 3. Un artículo se compra por $ 12, por lo que paga con $ 5, $ 3, $ 3 y $ 3 y se devuelve un cambio de $ 2.

Ya que seleccionamos las monedas más grandes primero, lo que no puedo entender es cómo saber si hay suficientes monedas de valor más bajo ($ 1 en este caso) en el inventario del jugador para dar cabida al ejemplo 1, y si no hay suficientes para usar más de las monedas de mayor valor como en el ejemplo 2.

Otro problema se ve en el siguiente ejemplo, aunque me encantaría que los dos ejemplos anteriores funcionen:

Ejemplo 3: El usuario lleva estas monedas: $ 5, $ 3, $ 3, $ 3. El jugador compra algo por $ 6. Sería mejor usar $ 3 y $ 3 y no devolver ningún cambio en lugar de usar $ 5 y $ 3 y dar $ 2 en cambio.

Creo que los dos primeros ejemplos se pueden resolver utilizando la recursión y una variación del algoritmo codicioso.

Para el premio de recompensa:

He agregado mi propia respuesta a continuación como una solución temporal por ahora. Sin embargo, me gusta el enfoque del Sr. Llama a continuación (vea el enlace al que hace referencia) y me gustaría encontrar un ejemplo de PHP para satisfacer esto. Creo que este enfoque no necesita recursión y utiliza la memorización.

Si hay múltiples opciones para la menor cantidad de cambio, me gustaría que el empate se otorgue a la que paga con la menor cantidad de monedas.

Answer 1

El problema se puede definir como:

Return a subset of items where the sum is closest to x, but >= x.

Este problema se llama el problema de suma de subconjunto. Es NP-completo. No encontrará un algoritmo perfecto que se ejecute en tiempo pseudo-polinomial, solo heurística imperfecta.

Sin embargo, si el número de monedas es muy pequeño, entonces una búsqueda exhaustiva del espacio de la solución funcionará.

Si el número de monedas es mayor, entonces debería buscar en Wikipedia un resumen: https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm

Answer 2

Esta es mi solución. No sé qué tan eficiente es, pero funciona, estoy abierto a sugerencias.

<?php

    $player=array(0,3,1,0);//how much coins you have
    $player_copy=$player;
    $coin_count=array(0,0,0,0);//memorize which coins you gave
    $coin_value=array(1,3,5,10);
    $price=6;       //price of item
    $price_copy=$price;
    $z=3;
    $change=array(-1,-1,-1,-1,-1); //memorise possible changes you can get
    $k=0;
    $flag=0;

label1: for($j=3;$j>=0;$j--){
            $coin_count[$j]=0;
            $player[$j]=$player_copy[$j];
        }
        for($j=$z;$j>=0;$j--){
            while(($price>0) && 1<=$player[$j]){
                $price-=$coin_value[$j];
                $player[$j]--;
                $coin_count[$j]++;
            }
        }
        $change[$k++]=$price;
         if($price!=0){
                for($j=$z;$j>=0;$j--)
                    if($price_copy>$coin_value[$j]){
                        $z=$j-1;
                        $price=$price_copy;
                        goto label1;
                    }
                $flag=1;
         }
    //find minimum change 
        $minv=$change[0];

         for($i=1;$change[$i]>=0 and $i<4;$i++)
             if($change[$i]>$minv)
                $minv=$change[$i];
         $i;
  //when you find minimum change find which coins you have used
         for($i=0;$i<4;$i++)
             if($change[$i]==$minv && $flag==1){
                $flag=2;
                for($j=3;$j>=0;$j--){//reset coin_count and player budget
                    $coin_count[$j]=0;
                    $player[$j]=$player_copy[$j];
                }
                 for($j=3-($i%2)-1;$j>=0;$j--){
                     while(($price>0) && 1<=$player[$j]){
                         $price-=$coin_value[$j];
                         $player[$j]--;
                         $coin_count[$j]++;
                     }
                  }
              }
//prints result
         for($j=0;$j<4;$j++)
            printf("%d x %d/n",$coin_count[$j],$coin_value[$j]);
         printf("change: %d/n",$minv);
?>

Answer 3

Esta respuesta se basa en la respuesta de גלעד-ברקן. Lo estoy publicando aquí según su petición. Si bien ninguna de las respuestas fue la que estaba buscando, descubrí que esta era la mejor opción publicada. Aquí está el algoritmo modificado que estoy usando actualmente:

<?php

function leastChange($inventory, $price){

    //NOTE: Hard coded these in the function for my purposes, but $coin value can be passed as a parameter for a more general-purpose algorithm
    $num_coin_types = 4;
    $coin_value = [10,5,3,1];

    $have = 0;
    for ($i=0; $i < $num_coin_types; $i++){
            $have += $inventory[$i] * $coin_value[$i];
    }

    //NOTE: Check to see if you have enough money to make this purchase
    if ($price > $have){
            $error = ["error", "Insufficient Funds"];
            return $error;
    }

    $stack = [[0,$price,$have,[]]];
    $best = [-max($coin_value),[]];

    while (!empty($stack)){

            // each stack call traverses a different set of parameters
            $parameters = array_pop($stack);

            $i = $parameters[0];
            $owed = $parameters[1];
            $have = $parameters[2];
            $result = $parameters[3];

            if ($owed <= 0){
                    //NOTE: check for new option with least change OR if same as previous option check which uses the least coins paid
                    if ($owed > $best[0] || ($owed == $best[0] && (array_sum($result) < array_sum($best[1])))){

                            //NOTE: add extra zeros to end if needed
                            while (count($result) < 4){
                                    $result[] = 0;
                            }
                            $best = [$owed,$result];
                    }
                    continue;
            }

            // skip if we have none of this coin
            if ($inventory[$i] == 0){
                    $result[] = 0;
                    $stack[] = [$i + 1,$owed,$have,$result];
                    continue;
            }

            // minimum needed of this coin
            $need = $owed - $have + $inventory[$i] * $coin_value[$i];

            if ($need < 0){
                    $min = 0;
            } else {
                    $min = ceil($need / $coin_value[$i]);
            }

            // add to stack
            for ($j=$min; $j<=$inventory[$i]; $j++){
                    $stack[] = [$i + 1,$owed - $j * $coin_value[$i],$have - $inventory[$i] * $coin_value[$i],array_merge($result,[$j])];
                    if ($owed - $j * $coin_value[$i] < 0){
                            break;
                    }
            }
    }

    return $best;
}

Aquí está mi código de prueba:

$start = microtime(true);

$inventory = [0,1,3,4];
$price = 12;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";



$inventory = [0,1,4,0];
$price = 12;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";

$inventory = [0,1,4,0];
$price = 6;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";


$inventory = [0,1,4,0];
$price = 7;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";


$inventory = [1,3,3,10];
$price=39;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";

$inventory = [1,3,3,10];
$price=45;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";

//stress test
$inventory = [25,25,25,1];
$price=449;
echo "/n";
echo json_encode(leastChange($inventory,$price));
echo "/n";

$time_elapsed = microtime(true) - $start;
echo "/n Time taken: $time_elapsed /n";

El resultado:

[0,[0,1,2,1]]

[0,[0,0,4,0]]

[0,[0,0,2,0]]

[-1,[0,1,1,0]]

[0,[1,3,3,5]]

["error","Insufficient Funds"]

[-1,[25,25,25,0]]

Time taken: 0.0046839714050293

¡Por supuesto que el tiempo está en microsegundos y, por lo tanto, se ejecutó en una fracción de segundo!

Answer 4

La solución que pude hacer cubre los 3 ejemplos publicados en su pregunta. Y siempre da el cambio con la menor cantidad de monedas posible.

Las pruebas que hice parecían ser ejecutadas muy rápido.

Aquí publico el código:

<?php

//Example values
$coin_value = array(10,5,3,1);
$inventory = array(5,4,3,0);
$price = 29;

//Initialize counters
$btotal = 0;
$barray = array(0,0,0,0);

//Get the sum of coins
$total_coins = array_sum($inventory);

function check_availability($i) {
    global $inventory, $barray;
    $a = $inventory[$i];
    $b = $barray[$i];
    $the_diff = $a - $b;
    return $the_diff != 0;
}

/*
 * Checks the lower currency available
 * Returns index for arrays, or -1 if none available
 */
function check_lower_available() {
    for ($i = 3; $i >= 0; $i--) {
        if (check_availability($i)) {
            return $i;
        }
    }
    return -1;
}

for($i=0;$i<4;$i++) {
    while(check_availability($i) && ($btotal + $coin_value[$i]) <= $price) {
        $btotal += $coin_value[$i];
        $barray[$i]++;
    }
}

if($price != $btotal) {
    $buf = check_lower_available();
    for ($i = $buf; $i >= 0; $i--) {
        if (check_availability($i) && ($btotal + $coin_value[$i]) > $price) {
            $btotal += $coin_value[$i];
            $barray[$i]++;
            break;
        }
    }
}

// Time to pay
$bchange = 0;
$barray_change = array(0,0,0,0);

if ($price > $btotal) {
    echo "You have not enough money.";
}
else {
    $pay_msg = "You paid $".$btotal."/n/n";
    $pay_msg.= "You used ".$barray[0]." coins of $10/n";
    $pay_msg.= "You used ".$barray[1]." coins of $5/n";
    $pay_msg.= "You used ".$barray[2]." coins of $3/n";
    $pay_msg.= "You used ".$barray[3]." coins of $1/n/n/n";
    // Time to give change
    $the_diff = $btotal - $price;
    if (!empty($the_diff)) {
        for ($i = 0; $i < 4; $i++) {
            while($the_diff >= $coin_value[$i]) {
                $bchange += $coin_value[$i];
                $barray_change[$i]++;
                $the_diff -= $coin_value[$i];
            }
        }

        $check_sum = array_sum($inventory) - array_sum($barray);
        $check_sum+= array_sum($barray_change);
        $msg = "";
        if ($check_sum < 15) {
            $change_msg = "Your change: $".$bchange."/n/n";
            $change_msg.= "You received ".$barray_change[0]." coins of $10/n";
            $change_msg.= "You received ".$barray_change[1]." coins of $5/n";
            $change_msg.= "You received ".$barray_change[2]." coins of $3/n";
            $change_msg.= "You received ".$barray_change[3]." coins of $1/n/n";
            $msg = $pay_msg.$change_msg;
        }
        else {
            $msg = "You have not enough space to hold the change./n";
            $msg.= "Buy cancelled./n";
        }
    }
    else {
        $msg = $pay_msg."You do not need change/n";
    }
    if ($check_sum < 15) {
        for ($i = 0; $i < 4; $i++) {
            $inventory[$i] -= $barray[$i];
            $total_coins-= $barray[$i];
        }
        for ($i = 0; $i < 4; $i++) {
            $inventory[$i] += $barray_change[$i];
            $total_coins+= $barray[$i];
        }
    }
    echo $msg;
    echo "Now you have:/n";
    echo $inventory[0]." coins of $10/n";
    echo $inventory[1]." coins of $5/n";
    echo $inventory[2]." coins of $3/n";
    echo $inventory[3]." coins of $1/n";
}

Answer 5

No sé PHP, así que lo he probado en Java. Espero que esté bien ya que es el algoritmo que es importante.

Mi código es el siguiente:

package .changecalculator;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ChangeCalculator
{
    List<Integer> coinsInTil = new ArrayList<>();

    public void setCoinsInTil(List<Integer> coinsInTil)
    {
        this.coinsInTil = coinsInTil;
    }

    public Map<String, List> getPaymentDetailsFromCoinsAvailable(final int amountOwed, List<Integer> inPocketCoins)
    {
        List<Integer> paid = new ArrayList<>();
        int remaining = amountOwed;

        // Check starting with the largest coin.
        for (Integer coin : inPocketCoins)
            if (remaining > 0 && (remaining - coin) >= 0) {
                    paid.add(coin);
                    remaining = remaining - coin;
            }

        ProcessAlternative processAlternative = new ProcessAlternative(amountOwed, inPocketCoins, paid, remaining).invoke();
        paid = processAlternative.getPaid();
        remaining = processAlternative.getRemaining();

        removeUsedCoinsFromPocket(inPocketCoins, paid);
        int changeOwed = payTheRestWithNonExactAmount(inPocketCoins, paid, remaining);
        List<Integer> change = calculateChangeOwed(changeOwed);

        Map<String, List> result = new HashMap<>();
        result.put("paid", paid);
        result.put("change", change);
        return result;
    }

    private void removeUsedCoinsFromPocket(List<Integer> inPocketCoins, List<Integer> paid)
    {
        for (int i = 0; i < inPocketCoins.size(); i++) {
            Integer coin = inPocketCoins.get(i);
            if (paid.contains(coin))
                inPocketCoins.remove(i);
        }
    }

    private List<Integer> calculateChangeOwed(int changeOwed)
    {
        List<Integer> change = new ArrayList<>();
        if (changeOwed < 0) {
            for (Integer coin : coinsInTil) {
                if (coin + changeOwed == 0) {
                    change.add(coin);
                    changeOwed = changeOwed + coin;
                }
            }
        }
        return change;
    }

    private int payTheRestWithNonExactAmount(List<Integer> inPocketCoins, List<Integer> paid, int remaining)
    {
        if (remaining > 0) {
            for (int coin : inPocketCoins) {
                while (remaining > 0) {
                    paid.add(coin);
                    remaining = remaining - coin;
                }
            }
        }
        return remaining;
    }
}

La clase ProcessAlternative maneja los casos en los que la moneda más grande no nos permite obtener un caso donde no se devuelva ningún cambio, por lo que intentamos una alternativa.

package .changecalculator;

import java.util.ArrayList;
import java.util.List;

// if any remaining, check if we can pay with smaller coins first.
class ProcessAlternative
{
    private int amountOwed;
    private List<Integer> inPocketCoins;
    private List<Integer> paid;
    private int remaining;

    public ProcessAlternative(int amountOwed, List<Integer> inPocketCoins, List<Integer> paid, int remaining)
    {
        this.amountOwed = amountOwed;
        this.inPocketCoins = inPocketCoins;
        this.paid = paid;
        this.remaining = remaining;
    }

    public List<Integer> getPaid()
    {
        return paid;
    }

    public int getRemaining()
    {
        return remaining;
    }

    public ProcessAlternative invoke()
    {
        List<Integer> alternative = new ArrayList<>();
        int altRemaining = amountOwed;
        if (remaining > 0) {
            for (Integer coin : inPocketCoins)
                if (altRemaining > 0 && factorsOfAmountOwed(amountOwed).contains(coin)) {
                    alternative.add(coin);
                    altRemaining = altRemaining - coin;
                }
            // if alternative doesn''t require change, use it.
            if (altRemaining == 0) {
                paid = alternative;
                remaining = altRemaining;
            }
        }
        return this;
    }

    private ArrayList<Integer> factorsOfAmountOwed(int num)
    {
        ArrayList<Integer> aux = new ArrayList<>();
        for (int i = 1; i <= num / 2; i++)
            if ((num % i) == 0)
                aux.add(i);
        return aux;
    }
}

Trabajé en él haciendo una prueba para el ejemplo 1, luego para el ejemplo 2 y, por último, pasé al ejemplo 3. El bit de la alternativa de proceso se agregó aquí y la alternativa para las monedas de prueba originales devolvió 0 cambios necesarios, por lo que actualicé la cantidad de entrada a 15 en lugar de 12 para que calcule el cambio requerido.

Las pruebas son las siguientes:

package .changecalculator;

import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class ChangeCalculatorTest
{
    public static final int FIFTY_PENCE = 0;
    public static final int TWENTY_PENCE = 1;
    public static final int TEN_PENCE = 2;
    public static final int FIVE_PENCE = 3;
    public static final int TWO_PENCE = 4;
    public static final int PENNY = 5;

    public ChangeCalculator calculator;

    @Before
    public void setUp() throws Exception
    {
        calculator = new ChangeCalculator();
        List<Integer> inTil = new ArrayList<>();
        inTil.add(FIFTY_PENCE);
        inTil.add(TWENTY_PENCE);
        inTil.add(TEN_PENCE);
        inTil.add(FIVE_PENCE);
        inTil.add(TWO_PENCE);
        inTil.add(PENNY);
        calculator.setCoinsInTil(inTil);
    }

    @Test
    public void whenHaveExactAmount_thenNoChange() throws Exception
    {
        // $5, $3, $3, $3, $1, $1, $1, $1
        List<Integer> inPocket = new ArrayList<>();
        inPocket.add(5);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(1);
        inPocket.add(1);
        inPocket.add(1);
        inPocket.add(1);

        Map<String, List> result = calculator.getPaymentDetailsFromCoinsAvailable(12, inPocket);

        List change = result.get("change");
        assertTrue(change.size() == 0);
        List paid = result.get("paid");
        List<Integer> expected = new ArrayList<>();
        expected.add(5);
        expected.add(3);
        expected.add(3);
        expected.add(1);
        assertEquals(expected, paid);
    }

    @Test
    public void whenDoNotHaveExactAmount_thenChangeReturned() throws Exception {
        // $5, $3, $3, $3, $3
        List<Integer> inPocket = new ArrayList<>();
        inPocket.add(5);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);

        Map<String, List> result = calculator.getPaymentDetailsFromCoinsAvailable(15, inPocket);

        List change = result.get("change");
        Object actual = change.get(0);
        assertEquals(2, actual);
        List paid = result.get("paid");
        List<Integer> expected = new ArrayList<>();
        expected.add(5);
        expected.add(3);
        expected.add(3);
        expected.add(3);
        expected.add(3);
        assertEquals(expected, paid);
    }

    @Test
    public void whenWeHaveExactAmountButItDoesNotIncludeBiggestCoin_thenPayWithSmallerCoins() throws Exception {
        // $5, $3, $3, $3
        List<Integer> inPocket = new ArrayList<>();
        inPocket.add(5);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);

        Map<String, List> result = calculator.getPaymentDetailsFromCoinsAvailable(6, inPocket);

        List change = result.get("change");
        assertTrue(change.size() == 0);
        List paid = result.get("paid");
        List<Integer> expected = new ArrayList<>();
        expected.add(3);
        expected.add(3);
        assertEquals(expected, paid);
    }
}

Las pruebas aún no son las más limpias, pero todas están pasando hasta ahora. Puedo regresar y agregar más casos de prueba más tarde para ver si puedo romperlo pero no tengo tiempo ahora.

Answer 6

Puedes usar una pila para enumerar combinaciones válidas. La versión a continuación utiliza una pequeña optimización, calculando si se necesita un mínimo de la denominación actual. Se devuelven más de una combinación de cambio mínimo, si hay alguna, que podría restringirse con la memoria; también se podría agregar una salida temprana si la denominación actual pudiera completar la combinación con cambio cero. Espero que el código comónicamente se explique por sí mismo (avíseme si desea una explicación más detallada):

function leastChange($coin_value,$inventory,$price){
  $n = count($inventory);
  $have = 0;
  for ($i=0; $i<$n; $i++){
    $have += $inventory[$i] * $coin_value[$i];
  }

  $stack = [[0,$price,$have,[]]];
  $best = [-max($coin_value),[]];

  while (!empty($stack)){

    // each stack call traverses a different set of parameters
    $parameters = array_pop($stack);
    $i = $parameters[0];
    $owed = $parameters[1];
    $have = $parameters[2];
    $result = $parameters[3];

    // base case
    if ($owed <= 0){
      if ($owed > $best[0]){
        $best = [$owed,$result];
      } else if ($owed == $best[0]){

        // here you can add a test for a smaller number of coins

        $best[] = $result;
      }
      continue;
    }

    // skip if we have none of this coin
    if ($inventory[$i] == 0){
      $result[] = 0;
      $stack[] = [$i + 1,$owed,$have,$result];
      continue;
    }

    // minimum needed of this coin
    $need = $owed - $have + $inventory[$i] * $coin_value[$i];

    if ($need < 0){
      $min = 0;
    } else {
      $min = ceil($need / $coin_value[$i]);
    }

    // add to stack
    for ($j=$min; $j<=$inventory[$i]; $j++){
      $stack[] = [$i + 1,$owed - $j * $coin_value[$i],$have - $inventory[$i] * $coin_value[$i],array_merge($result,[$j])];
      if ($owed - $j * $coin_value[$i] < 0){
        break;
      }
    }
  }

  return $best;
}

Salida:

$coin_value = [10,5,3,1];
$inventory = [0,1,3,4];
$price = 12;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,1,2,1],[0,1,1,4],[0,0,3,3]]

$coin_value = [10,5,3,1];
$inventory = [0,1,4,0];
$price = 12;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,0,4]]

$coin_value = [10,5,3,1];
$inventory = [0,1,3,0];
$price = 6;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,0,2]]

$coin_value = [10,5,3,1];
$inventory = [0,1,3,0];
$price = 7;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [-1,[0,1,1]]

Actualizar:

Ya que también está interesado en el menor número de monedas, creo que la memorización solo podría funcionar si podemos garantizar que no se omitirá una mejor posibilidad. Creo que esto se puede hacer si realizamos nuestra primera búsqueda en profundidad utilizando primero las monedas más grandes que podamos. Si ya logramos la misma suma usando monedas más grandes, no tiene sentido continuar con el hilo actual. Asegúrese de que el inventario de entrada presente monedas clasificadas en orden descendente de tamaño de denominación y agregue / cambie lo siguiente:

// maximum needed of this coin
$max = min($inventory[$i],ceil($owed / $inventory[$i]));

// add to stack 
for ($j=$max; $j>=$min; $j--){

Answer 7

Se me ha ocurrido la siguiente solución. Si otros pueden criticarlo por mí, lo apreciaría.

<?php

$coin_value = array(10,5,3,1);
$inventory = array(1,2,0,2);
$price = 17;

for ($i = 3; $i >= 0; $i--){

        $btotal = 0;
        $barray = array();

        for ($j = 0; $j < 4; $j++){
                $remaining = $price - $btotal;
                $to_add = floor($remaining / $coin_value[$j]);

                if ($i != 3 && $i == $j){
                        $to_add++;
                }

                if ($inventory[$j] < $to_add){
                        $to_add = $inventory[$j];
                }

                $btotal += $to_add * $coin_value[$j];

                for ($k = 0; $k < $to_add; $k++){
                        $barray[] = $coin_value[$j];
                }

                if ($btotal >= $price)
                        break 2; //warning: breaks out of outer loop

        }
}

$change_due = $btotal - $price;

print_r($barray);

echo "Change due: /$$change_due/n";

?>

Cubre los ejemplos 1 y 2 en mi pregunta original, pero no cubre el ejemplo 3. Sin embargo, creo que funcionará por ahora a menos que alguien pueda encontrar una solución mejor. Decidí no usar la recursión ya que parecería tomar demasiado tiempo.

Answer 8

Tuve un problema similar, excepto que en lugar de que se me permitiera repasar, la combinación tenía que permanecer por debajo de la cantidad objetivo. Al final, utilicé el enfoque dinámico presentado en esta respuesta . Usted debe ser capaz de usarlo también.

Es algo parecido a esto:

1. Comience con una lista que consiste en un solo elemento vacío.
2. Para cada entrada en la lista ...
   1. Copie la entrada y agregue la primera moneda (¡no el valor de la moneda!) Que no contiene.
   2. Almacene el nuevo elemento en la lista original si y solo si * su nuevo valor de suma ya no existe en la lista.
3. Repita el paso 2 hasta que haga un pase donde no se agreguen nuevos elementos a la lista
4. Iterar la lista de resultados y mantener la mejor combinación (según sus criterios)

*: Podemos hacer esta optimización porque no nos importa particularmente qué monedas se usan en la combinación, solo el valor de la suma de la colección de monedas.

El algoritmo anterior se puede optimizar un poco si usa el valor de la suma como la clave.