Le nombre minimum de pièces de monnaie dont la somme est S
https://stackoverflow.com/questions/4247662
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné une liste de pièces N, leurs valeurs (V1, V2, ..., VN), et la somme totale S. Trouver le nombre minimum de pièces dont la somme est S (on peut utiliser autant de pièces de un type que nous voulons), ou d'un rapport qu'il est impossible de sélectionner des pièces de monnaie dans une telle manière que leur somme à S.
J'essaie de comprendre la programmation dynamique, ne l'ont pas compris. Je ne comprends pas l'explication donnée, alors peut-être que vous pouvez me jeter quelques conseils comment programmer cette tâche? Aucun code, seulement des idées où je devrais commencer.
Merci.
La solution
Ceci est un problème classique Knapsack, jetez un oeil ici pour quelques informations supplémentaires: Wikipedia problème Knapsack
Vous devriez également regarder un certain tri, le tri spécifiquement de la plus grande à la plus petite valeur.
Autres conseils
La réponse précise à ce problème est bien expliqué ici. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
Comme nous l'avons souligné, la programmation dynamique convient le mieux à ce problème. J'ai écrit un programme Python pour ceci: -
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)
Pour l'entrée:
12
2 3 5
La sortie serait:
[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3]
3
Le list_index est le total nécessaire et la valeur à list_index est pas. des pièces nécessaires pour obtenir ce total. La réponse à au-dessus de l'entrée (obtenir une valeur 12) est de 3 (pièces de monnaie de valeurs 5, 5, 2).
Je pense que l'approche que vous voulez est comme ceci:
Vous savez que vous voulez produire une S somme. Les seuls moyens de produire S sont d'abord produits S-V1, puis ajoutez une pièce de monnaie de valeur V1; ou pour produire S-V2, puis ajoutez une pièce de monnaie de valeur V2; ou ...
À son tour, T=S-V1 est productible de T-V1 ou T-V2, ou ...
En reculant de cette façon, vous pouvez déterminer la meilleure façon, le cas échéant, pour produire S de vos Vs.
Question est déjà répondu, mais je voulais fournir le code de travail C que je l'ai écrit, si cela aide tout le monde. enter code here
Code a dur codé d'entrée, mais il est juste de le garder simple. La solution finale est le min tableau contenant le nombre de pièces nécessaires pour chaque somme.
#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();
}
Je ne sais pas sur la programmation dynamique, mais c'est ainsi que je le ferais. À partir de zéro et travailler votre chemin vers S. Produire un ensemble avec une pièce de monnaie, puis avec ce jeu produire un ensemble de deux pièces, et ainsi de suite ... Rechercher S, et ignorer toutes les valeurs supérieures S. Pour chaque valeur se rappeler le nombre de pièces utilisées.
Beaucoup de gens déjà répondu à la question. Voici un code qui utilise 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;
}
L'idée principale est - pour chaque j, la valeur pièce [j] <= i (ie somme) nous regardons le nombre minimum de pièces trouvé pour i-valeur [j] (disons m) somme (précédemment trouvé) . Si m + 1 est inférieur au nombre minimum de pièces déjà trouvées pour la somme actuelle i nous mettre à jour le nombre de pièces dans le tableau.
Ex - somme = 11 n = 3 et de la valeur [] = {1,3,5}
Ce qui suit est la sortie que nous obtenons
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
Comme on peut le constater pour la somme i = 3, 5, 8 et 10 nous améliorer de notre minimum précédent de manière suivante -
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.
Donc, pour somme = 11 nous allons obtenir la réponse que 3 (5 + 5 + 1).
Voici le code C. Son similaire à pseudocode donnée dans la page TopCoder dont la référence est prévue dans l'une des réponses ci-dessus.
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);
}
Considérez i-ème pièce. Soit il sera inclus ou non. Si elle est incluse, la somme de la valeur est diminuée de la valeur de la pièce et le nombre de pièces utilisées augmente de 1. Si elle ne figure pas, alors nous devons explorer les pièces restantes de la même. Nous prenons le minimum de deux cas.
Je savais que c'est une vieille question, mais cela est une solution 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);
}
}
Pour une solution récursive rapide, vous pouvez vérifier ce lien: java solution
Je vais à travers les étapes minimales requises pour trouver la combinaison parfaite de pièces.
Disons que nous avons coins = [20, 15, 7] et monetaryValue = 37. Ma solution fonctionnera comme suit:
[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], 100652895656565)
