Die Mindestanzahl der Münzen, die die Summe beträgt S
https://stackoverflow.com/questions/4247662
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
eine Liste von N Münzen gegeben, deren Werte (V1, V2, ..., VN), und die Gesamtsumme S. die Mindestanzahl von Münzen finden, deren Summe S (wir so viele Münzen verwenden können eine Art, wie wir wollen), oder einen Bericht, dass es nicht möglich ist, Münzen in einer solchen Art und Weise zu wählen, dass sie zu S. zusammenzufassen
Ich versuche, die dynamische Programmierung zu verstehen, haben gedacht, es nicht aus. Ich verstehe nicht die gegebene Erklärung, vielleicht können Sie mir ein paar Hinweise werfen, wie diese Aufgabe zu programmieren? Kein Code, nur Ideen, wo ich anfangen soll.
Danke.
Lösung
Dies ist ein klassisches Knapsackproblem, werfen Sie einen Blick hier für einige weitere Informationen: Wikipedia Knapsack Problem
Sie sollten auch an einem gewissen Sortierung suchen, und zwar von der größten zur kleinsten Werte zu sortieren.
Andere Tipps
Die genaue Antwort auf dieses Problem ist auch hier erklärt. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
Wie bereits erwähnt, Dynamische Programmierung paßt am besten für dieses Problem. Ich habe ein Python-Programm für diese geschrieben: -
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)
Für die Eingabe:
12
2 3 5
Der Ausgang wäre:
[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3]
3
Die LIST_INDEX ist die Summe benötigt und der Wert bei LIST_INDEX ist die Nr. von Münzen benötigt, um diese Summe zu bekommen. Die Antwort für die oben Eingang (Wert 12 erhalten) 3 (Münzen von Werten 5, 5, 2).
Ich denke, der Ansatz, den Sie wollen, ist wie folgt:
Sie wissen, dass Sie eine Summe S produzieren wollen. Die einzigen Möglichkeiten zur Erzeugung S werden ersten produzieren S-V1, und dann eine Münze Wert V1 hinzuzufügen; oder S-V2 zu erzeugen und dann eine Münze Wert V2 hinzuzufügen; oder ...
Im Gegenzug ist T=S-V1 von T-V1 herstellbar oder T-V2, oder ...
Mit dem auf diese Weise ein Schritt zurück, können Sie die beste Art und Weise, wenn überhaupt, zu produzieren S von Ihrem Vs bestimmen.
Die Frage ist schon beantwortet, aber ich wollte arbeiten C-Code liefern, dass ich geschrieben habe, wenn es jemand hilft. enter code here
-Code eingegeben hart codiert, aber es ist nur um es einfach zu halten. Endlösung ist das Array min enthält die Anzahl der Münzen für jede Summe benötigt.
#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();
}
Ich weiß nicht, über die dynamische Programmierung, aber das ist, wie ich es tun würde. Starten von Null und arbeiten Sie sich nach S. Produzieren eines Satzes mit einer Münze, dann mit diesem Satz eine Zweimünzensatz erzeugen, und so weiter ... Suchen Sie nach S, und ignorieren alle Werte größer als S. erinnert Für jeden Wert der Anzahl der Münzen verwendet.
Viele Leute schon die Frage beantwortet. Hier ist ein Code, den DP verwendet
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;
}
Die Hauptidee ist - für jede Münze j, Wert [j] <= i (dh Summe) betrachten wir die Mindestanzahl von Münzen für i-Wert [j] (sagen wir mal m) Summe (bisher gefunden) gefunden . Wenn m + 1 ist kleiner als die minimale Anzahl von Münzen bereits für aktuelle Summe finde ich dann aktualisieren wir die Anzahl der Münzen in der Anordnung.
Für die Ex - sum = 11 n = 3 und Wert [] = {1,3,5}
Im Anschluss an die Ausgabe wir
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
Wie wir Summe beobachten i = 3, 5, 8 und 10 wir auf unserer vorherigen Mindest verbessern Wege in folgenden -
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.
Also für sum = 11 werden wir Antwort als 3 (5 + 5 + 1) erhalten.
Hier ist der Code in C. Seinem ähnlichen Pseudo-Code in TopCoder Seite gegeben, deren Referenz wird oben in eine der Antworten zur Verfügung gestellt.
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);
}
Betrachten i-ten Münze. Entweder es wird enthalten sein oder nicht. Wenn es enthalten ist, dann wird der Wert Summe durch die Münzwert und die Anzahl der verwendeten Münzen erhöht sich um 1 verringert, wenn sie nicht enthalten ist, dann müssen wir die restlichen Münzen in ähnlicher Weise erkunden. Wir nehmen die mindestens zwei Fälle.
Ich wusste, dass dies eine alte Frage, aber das ist eine Lösung in 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);
}
}
Für eine schnelle rekursive Lösung, können Sie diesen Link: java Lösung
Ich gehe durch die minimalen Schritte erforderlich, um die perfekte Kombination Münze zu finden.
Sagen wir coins = [20, 15, 7] und monetaryValue = 37 haben. Meine Lösung wird wie folgt funktionieren:
[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)
