El número mínimo de monedas de la suma de los cuales es S
https://stackoverflow.com/questions/4247662
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Dada una lista de N monedas, sus valores (V1, V2, ..., Vn), y la suma total de S. Encontrar el número mínimo de monedas de la suma de los cuales es S (podemos utilizar tantas monedas de un tipo que queramos), o un informe que no es posible seleccionar las monedas en una forma tal que se suman S.
Trato de entender la programación dinámica, no han figurado a cabo. No entiendo la explicación dada, por lo que tal vez se puede tirarme algunas pistas de cómo programar esta tarea? Ningún código, sólo las ideas donde debería comenzar.
Gracias.
Solución
Este es un problema clásico de la mochila, echar un vistazo aquí por algo más de información: Wikipedia mochila Problema
También debería mirar en alguna forma de selección, clasificación específica del más grande al más pequeño de los valores.
Otros consejos
La respuesta precisa a este problema está bien explicado aquí. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
Como ya se señaló, trajes de programación dinámica mejores para este problema. He escrito un programa 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 list_index es el total que se necesita y el valor al list_index es el no. de monedas necesarias para conseguir ese total. La respuesta para encima de la Entrada (obtener un valor 12) es de 3 (monedas de valores de 5, 5, 2).
Creo que el enfoque que queremos es la siguiente:
Usted sabe que usted quiere producir un S suma. La única manera de S productos son de primera S-V1 producto, y luego añadir una moneda de valor V1; o para producir S-V2 y luego añadir una moneda de valor V2; o ...
A su vez, se puede producir a partir T=S-V1 T-V1 o T-V2, o ...
Por dar un paso atrás de esta manera, se puede determinar la mejor manera, en su caso, a partir de sus productos S Vs.
Pregunta ya está contestada pero quería que permite un trabajo código C que he escrito, si ayuda a nadie. enter code here
Código ha codificado de entrada, pero es sólo para mantener la sencillez. La solución final es el min matriz 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();
}
No sé acerca de la programación dinámica, pero esta es la forma en que lo haría. Empezar desde cero y su forma de trabajo a S. Producir un conjunto con una moneda, y luego con ese conjunto producen un conjunto de dos monedas, y así sucesivamente ... Buscar S, e ignorar todos los valores mayores S. Para cada valor de recordar el número de monedas utilizadas.
Hay mucha gente que ya ha respondido a la pregunta. Aquí es un código que utiliza 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;
}
La idea principal es - para cada moneda j, el valor de [j] <= i (es decir, suma) nos fijamos en el número mínimo de monedas encontradas para i-valor [j] (por no decir m) suma (previamente encontrado) . Si m + 1 es menor que el número mínimo de monedas que ya se encuentran a la suma de intensidades i entonces actualizamos el número de monedas en la matriz.
Para ex - suma = 11 n = 3 y el valor [] = {1,3,5}
A continuación se presenta la salida 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 por la suma i = 3, 5, 8 y 10 que la mejora sobre de nuestra anterior mínimo de las siguientes formas -
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.
Así que para la suma = 11 que obtendrá respuesta como 3 (5 + 5 + 1).
Aquí está el código en C. Su similar al pseudocódigo dada en la página TopCoder 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];
}
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);
}
Considere i-ésima moneda. Ya sea que se incluirá o no. Si se incluye, entonces la suma de valor se reduce por el valor de la moneda y el número de monedas aumenta utilizados por 1. Si no se incluye, entonces tenemos que explorar las monedas restantes de manera similar. Tomamos el mínimo de dos casos.
Yo sabía que esto es una cuestión de edad, 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);
}
}
Para una solución recursiva rápido, se puede comprobar este enlace: java solución
Voy a través de los pasos mínimos necesarios para encontrar la combinación perfecta de la moneda.
Digamos que tenemos coins = [20, 15, 7] y 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!
def leastCoins(lst, x):
temp = []
if x == 0:
return 0
else:
while x != 0:
if len(lst) == 0:
return "Not Possible"
if x % max(lst) == 0:
temp.append((max(lst), x//max(lst)))
x = 0
elif max(lst) < x:
temp.append((max(lst), x//max(lst)))
x = x % max(lst)
lst.remove(max(lst))
else:
lst.remove(max(lst))
return dict(temp)
leastCoins ([17,18,2], 100,652,895,656,565)
