algorithm - problems - how to solve a dynamic programming problem

El número mínimo de monedas cuya suma es S

Question

Dada una lista de N monedas, sus valores (V1, V2, ..., VN) y la suma total S. Encuentre el número mínimo de monedas cuya suma es S (podemos usar tantas monedas de un tipo como queremos), o informar que no es posible seleccionar monedas de tal manera que sumen a S.

Intento entender la programación dinámica, no lo he descubierto. No entiendo la explicación dada, así que tal vez puedas darme algunos consejos sobre cómo programar esta tarea. Sin código, solo ideas donde debería empezar.

Gracias.

Answer 1

Como ya se señaló, la programación dinámica se adapta mejor a este problema. He escrito un programa en Python para esto:

def sumtototal(total, coins_list):
    s = [0]
    for i in range(1, total+1):
        s.append(-1)
        for coin_val in coins_list:
            if i-coin_val >=0 and s[i-coin_val] != -1 and (s[i] > s[i-coin_val] or s[i] == -1):
                s[i] = 1 + s[i-coin_val]

    print s
    return s[total]

total = input()
coins_list = map(int, raw_input().split('' ''))
print sumtototal(total, coins_list)

Para la entrada:

12 2 3 5

La salida sería:

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3] 3 El índice de lista es el total necesario y el valor de índice de lista es el no. de monedas necesarias para obtener ese total. La respuesta para la entrada anterior (obtener un valor 12) es 3 (monedas de valores 5, 5, 2).

Answer 2

Creo que el enfoque que quieres es así:

Sabes que quieres producir una suma S Las únicas formas de producir S son producir primero S-V1 y luego agregar una moneda de valor V1 ; o para producir S-V2 y luego agregar una moneda de valor V2 ; o...

A su vez, T=S-V1 es producible desde T-V1 , o T-V2 , o ...

Al retroceder de esta manera, puede determinar la mejor manera, si existe, de producir S partir de sus V s.

Answer 3

Este es un problema clásico de mochila, eche un vistazo aquí para obtener más información: Wikipedia, el problema de mochila

También debe mirar algunos ordenamientos, específicamente los valores de Mayor a Menor.

Answer 4

La idea principal es: para cada moneda j, valor [j] <= i (es decir, suma), observamos el número mínimo de monedas encontradas para el valor i [j] (digamos m) suma (encontrada anteriormente). Si m + 1 es menor que el número mínimo de monedas ya encontradas para la suma actual i, entonces actualizamos el número de monedas en la matriz.

Por ejemplo: 11 n = 3 y valor [] = {1,3,5}
A continuación se muestra la salida que obtenemos.

i- 1  mins[i] - 1  
i- 2  mins[i] - 2  
i- 3  mins[i] - 3  
i- 3  mins[i] - 1  
i- 4  mins[i] - 2  
i- 5  mins[i] - 3  
i- 5  mins[i] - 1  
i- 6  mins[i] - 2  
i- 7  mins[i] - 3  
i- 8  mins[i] - 4  
i- 8  mins[i] - 2  
i- 9  mins[i] - 3  
i- 10 mins[i] - 4  
i- 10 mins[i] - 2  
i- 11 mins[i] - 3 

Como podemos observar para la suma i = 3, 5, 8 y 10, mejoramos de nuestro mínimo anterior de la siguiente manera:

sum = 3, 3 (1+1+1) coins of 1 to one 3 value coin  
sum = 5, 3 (3+1+1) coins to one 5 value coin  
sum = 8, 4 (5+1+1+1) coins to 2 (5+3) coins  
sum = 10, 4 (5+3+1+1) coins to 2 (5+5) coins.  

Entonces para la suma = 11 obtendremos la respuesta como 3 (5 + 5 + 1).

Aquí está el código en C. Es similar al pseudocódigo dado en la página de codificador superior cuya referencia se proporciona en una de las respuestas anteriores.

int findDPMinCoins(int value[], int num, int sum)
{
    int mins[sum+1];
    int i,j;

   for(i=1;i<=sum;i++)
       mins[i] = INT_MAX;

    mins[0] = 0;
    for(i=1;i<=sum;i++)
    {
        for(j=0;j<num;j++)
        {
            if(value[j]<=i && ((mins[i-value[j]]+1) < mins[i]))
            {
                mins[i] = mins[i-value[j]] + 1; 
                printf("i- %d  mins[i] - %d/n",i,mins[i]);
            }
        }
    }
    return mins[sum];
}

Answer 5

La pregunta ya está respondida pero quería proporcionar el código C en funcionamiento que escribí, si ayuda a alguien. enter code here

El código tiene una entrada codificada, pero es solo para mantenerlo simple. La solución final es la matriz mínima que contiene el número de monedas necesarias para cada suma.

#include"stdio.h"
#include<string.h>

int min[12] = {100};
int coin[3] = {1, 3, 5};

void
findMin (int sum) 
{
    int i = 0; int j=0;
    min [0] = 0; 

    for (i = 1; i <= sum; i++) {
        /* Find solution for Sum = 0..Sum = Sum -1, Sum, i represents sum
         * at each stage */
        for (j=0; j<= 2; j++) {
            /* Go over each coin that is lesser than the sum at this stage
             * i.e. sum = i */
            if (coin[j] <= i) {
                if ((1 + min[(i - coin[j])]) <= min[i]) { 
                    /* E.g. if coin has value 2, then for sum i = 5, we are 
                     * looking at min[3] */
                    min[i] = 1 + min[(i-coin[j])]; 
                    printf("/nsetting min[%d] %d",i, min[i]);
                }
            }
        }
    }
}
void
initializeMin()
{
    int i =0;
    for (i=0; i< 12; i++) {
        min[i] = 100;
    }
}
void
dumpMin() 
{
    int i =0;
    for (i=0; i< 12; i++) {
        printf("/n Min[%d]: %d", i, min[i]);
    }
}
int main() 
{
    initializeMin();
    findMin(11);
    dumpMin(); 
}

Answer 6

La respuesta precisa a este problema está bien explicada aquí. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Answer 7

Mucha gente ya respondió la pregunta. Aquí hay un código que usa DP

public static List<Integer> getCoinSet(int S, int[] coins) {
    List<Integer> coinsSet = new LinkedList<Integer>();
    if (S <= 0) return coinsSet;

    int[] coinSumArr = buildCoinstArr(S, coins);

    if (coinSumArr[S] < 0) throw new RuntimeException("Not possible to get given sum: " + S);

    int i = S;
    while (i > 0) {
        int coin = coins[coinSumArr[i]];
        coinsSet.add(coin);
        i -= coin;
    }

    return coinsSet;
}

public static int[] buildCoinstArr(int S, int[] coins) {
    Arrays.sort(coins);
    int[] result = new int[S + 1];

    for (int s = 1; s <= S; s++) {
        result[s] = -1;
        for (int i = coins.length - 1; i >= 0; i--) {
            int coin = coins[i];
            if (coin <= s && result[s - coin] >= 0) {
                result[s] = i;
                break;
            }
        }
    }

    return result;
}

Answer 8

No sé sobre programación dinámica, pero así es como lo haría. Empieza desde cero y avanza hacia S Produce un conjunto con una moneda, luego con ese conjunto produce un conjunto de dos monedas, y así sucesivamente ... Busca S , e ignora todos los valores mayores que S Para cada valor recuerda el número de monedas utilizadas.

Answer 9

Para una solución recursiva rápida, puede consultar este enlace: solución java

Estoy siguiendo los pasos mínimos necesarios para encontrar la combinación de monedas perfecta. Digamos que tenemos coins = [20, 15, 7] y valor monetaryValue = 37 . Mi solución funcionará de la siguiente manera:

[20] -> sum of array bigger than 37? NO -> add it to itself
[20, 20] greater than 37? YES (20 + 20) -> remove last and jump to smaller coin
[20, 15] 35 OK
[20, 15, 15] 50 NO
[20, 15, 7] 42 NO
// Replace biggest number and repeat
[15] 15 OK
[15, 15] 30 OK
[15, 15, 15] 45 NO
[15, 15, 7] 37! RETURN NUMBER!

Answer 10

Sabía que esta es una vieja pregunta, pero esta es una solución en Java.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class MinCoinChange {

    public static void min(int[] coins, int money) {
        int[] dp = new int[money + 1];
        int[] parents = new int[money + 1];
        int[] usedCoin = new int[money + 1];
        Arrays.sort(coins);
        Arrays.fill(dp, Integer.MAX_VALUE);
        Arrays.fill(parents, -1);

        dp[0] = 0;
        for (int i = 1; i <= money; ++i) {
            for (int j = 0; j < coins.length && i >= coins[j]; ++j) {
                if (dp[i - coins[j]] + 1 < dp[i]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                    parents[i] = i - coins[j];
                    usedCoin[i] = coins[j];
                }
            }
        }
        int parent = money;
        Map<Integer, Integer> result = new HashMap<>();
        while (parent != 0) {
            result.put(usedCoin[parent], result.getOrDefault(usedCoin[parent], 0) + 1);
            parent = parents[parent];
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        int[] coins = { 1, 5, 10, 25 };
        min(coins, 30);
    }
}

Answer 11

int getMinCoins(int arr[],int sum,int index){

        int INFINITY=1000000;
        if(sum==0) return 0;
        else if(sum!=0 && index<0) return INFINITY;

        if(arr[index]>sum) return getMinCoins(arr, sum, index-1);

        return Math.min(getMinCoins(arr, sum, index-1), getMinCoins(arr, sum-arr[index], index-1)+1);
    }

Considera la moneda i-th. O se incluirá o no. Si se incluye, entonces la suma del valor se reduce con el valor de la moneda y el número de monedas utilizadas aumenta en 1. Si no está incluido, debemos explorar las monedas restantes de manera similar. Tomamos el mínimo de dos casos.