Минимальное количество монет сумма которого является S
https://stackoverflow.com/questions/4247662
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая список N монет, их значения (V1, V2, ..., Vn) и общая сумма S. Найдите минимальное количество монет, сумма которой является S (мы можем использовать столько монет одного типа, как Мы хотим), или сообщите, что невозможно выбрать монеты таким образом, что они суммируют до S.
Я пытаюсь понять динамическое программирование, не понял его. Я не понимаю данного объяснения, так что, возможно, вы можете бросить мне несколько советов, как программировать эту задачу? Нет кода, просто идеи, где я должен начать.
Спасибо.
Решение
Это классическая проблема рюкзака, посмотрите здесь еще для получения дополнительной информации: Проблема Wikipedia Knaxackack
Вы также должны посмотреть на какую-то сортировку, специально сортирующие от самых больших до наименьших ценностей.
Другие советы
Точный ответ на эту проблему хорошо объяснено здесь.http://www.topcoder.com/tc?module=static&d1=tutorials&d2=dynProg
Как уже указано, динамическое программирование подходит для этой проблемы. Я написал программу Python для этого: -
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)
Для ввода:
12
2 3 5
Вывод будет:
[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3]
3
List_index - это общий необходимый, а значение в List_index - нет. монеты, необходимые для того, чтобы получить это всего. Ответ для вышеуказанного входа (получение значения 12) составляет 3 (монеты значений 5, 5, 2).
Я думаю, что подход, который вы хотите, это так:
Вы знаете, что вы хотите произвести сумму S. Отказ Единственные способы изготовления S должны сначала производить S-V1, а затем добавьте монету V1; или производить S-V2 а затем добавьте монету ценности V2; или...
По очереди, T=S-V1 не производится T-V1, или T-V2, или...
Наступая в этот путь, вы можете определить лучший способ, если таковые имеются, производить S от твоего Vс.
Вопрос уже ответил, но я хотел обеспечить рабочее C-код, который я написал, если это кому-либо поможет. enter code here
Код имеет жесткий код ввода, но это просто просто просто. Окончательное решение - это массив min, содержащий количество монет, необходимых для каждой суммы.
#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();
}
Я не знаю о динамическом программировании, но это то, как я это сделаю. Начать с нуля и работать на пути к S. Отказ Создайте набор с одной монетой, затем с помощью этого набора создают набор двух монет, и так далее ... поиск S, и игнорируйте все значения, превышающие S. Отказ Для каждого значения запомните количество используемых монет.
Многие люди уже ответили на вопрос. Вот код, который использует 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;
}
Основная идея - для каждой монеты j, значение [j] <= i (т. Е. Сумма). Мы посмотрим на минимальное количество монет, найденных для I-значения [J] (Let m) сумма (ранее найден). Если M + 1 меньше минимального количества монет, уже найденных для текущей суммы I, то мы обновляем количество монет в массиве.
Для ex - сумма = 11 n = 3 и значение [] = {1,3,5}
Ниже приведены выходные данные, которые мы получаем
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
Как мы можем наблюдать за суммой i = 3, 5, 8 и 10, мы улучшаемся от нашего предыдущего минимума следующими способами -
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.
Так что для Sum = 11 мы получим ответ как 3 (5 + 5 + 1).
Вот код в C. Это похоже на псевдокод, приведенный на странице TopCoder, ссылка на одну из ответов выше.
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);
}
Рассмотрим я монету. Либо это будет включено или нет. Если он включен, то сумма стоимости уменьшается по значению монеты, а количество используемых монет увеличивается на 1. Если он не включен, то нам нужно исследовать оставшиеся монеты аналогично. Мы берем минимальные два случая.
Я знал, что это старый вопрос, но это решение в 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);
}
}
Для быстрого рекурсивного решения вы можете проверить эту ссылку: Java-решение
Я прохожу через минимальные шаги, необходимые для поиска идеальной комбинации монет. Скажем, у нас есть coins = [20, 15, 7] а также monetaryValue = 37. Отказ Мое решение будет работать следующим образом:
[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)
наименошества ([17,18,2], 100652895656565)
