Максимальное значение почтовых марок на конверте
https://stackoverflow.com/questions/3826975
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Проблема почтовой марки - это математическую загадку, которая спрашивает, каково самое наименьшее значение почтового расчета, которое не может быть помещено на конверте, если письмо может удерживать только ограниченное количество штампов, и они могут иметь только определенные указанные значения для лица.
Например, предположим, что конверт может удерживать только три марки, а имеющиеся значения штампов представляют собой 1 цент, 2 цента, 5 центов и 20 центов. Тогда решение составляет 13 центов; Поскольку любое меньшее значение может быть получено с большинства трех штампов (например, 4 = 2 + 2, 8 = 5 + 2 + 1 и т. Д.), Но чтобы получить 13 центов, нужно использовать как минимум четыре штампа.
Существует ли алгоритм, который дал максимальное количество мармок, разрешенных и значением марок, можно найти самые маленькие почтовые расходы, которые не могут быть размещены на конверте?
Другой пример:
Максимум 5 марок можно использовать
Цели: 1, 4, 12, 21
Наименьшее значение, которое невозможно достичь, составляет 72. Значения 1-71 могут быть созданы с определенной комбинацией.
В конце концов, я, вероятно, буду использовать Java для того, чтобы кодировать это.
Решение
Да, есть такой алгоритм. Наивно: начиная с 1, попробуйте все возможное сочетание марок до тех пор, пока мы не найдем комбинацию, которая дает сумму 1, то попробуйте 2, и так далее. Ваш алгоритм заканчивается, когда он находит такой номер, что никакие комбинации марок не добавляют к этому номеру.
Потому что, возможно, медленно, для небольших проблем (скажем, 100 штемпелей, 10 позиций) Вы можете решить это в «разумном» количестве ...
Но для больших проблем, в тех, где у нас есть много штамп (говорит 1000-х), и многие возможные позиции (говорят 1000), этот алгоритм может принять неразрешенное количество времени. То есть для очень больших проблем, время решать проблему, используя этот подход, может сказать, что жизнь вселенной, и, таким образом, это не очень полезно для вас.
Если у вас действительно большие проблемы, вам нужно найти способы ускорить поиск, эти ускорения называются эвристикой. Вы не можете победить проблему, но вы можете решить проблему быстрее, чем наивный подход, применяя некоторые знания домена.
Простой способ улучшить этот наивный подход, может заключаться в том, что в любое время вы пытаетесь комбинацию штампов, которые не равен нуме, вы ищете, вы удалите эту комбинацию от возможного набора, чтобы попробовать для любого будущего номера, и отметьте это будущее номер как недоступен. Сказал еще один способ: сохранить список номеров, которые вы нашли уже, и комбинации, которые посещали вас туда, то не ищите эти цифры или их комбинации.
Другие советы
Вот еще один совет: Каждый набор штампов, которые добавляют до некоторого данного номера, могут быть сформированы путем добавления 1 штампов к набору марки минимально размером, которые добавляют до меньшего количества.
Например, предположим, что у нас есть марки 1, 2, 7, 12 и 50 и предел 5 марок, и мы хотим выяснить, можно ли представить 82. Чтобы получить это 82, вы должны добавить либо:
- A 1 на набор штампов, добавляющих до 82-1 = 81 или
- A 2 до набора штампов, добавляющих до 82-2 = 80, или
- 7 до набора штампов, добавляющих до 82-7 = 75, или
- 12 до набора марок, добавляющих до 82-12 = 70, или
- A 50 до набора штампов, добавляющих до 82-50 = 32.
Это единственные возможные способы сформированы 82. Среди всех этих 5 возможностей, один (или, возможно, более чем один) будет иметь минимальное количество штампов. Если это минимальное число> 5, то 82 не может быть представлено штаммами.
Обратите внимание, что если номер может быть представлен, вам необходимо записать минимальное количество штампов, необходимых для него, чтобы расчеты для более высоких чисел могут использовать его.
Это плюс Ответ Стив Джессопа, надеюсь, вы получите ваш разум на правильном пути для динамического программирования решения ... Если вы все еще тупитесь, дайте мне знать.
Вместо того, чтобы исчерпывающие вычислительные суммы всех возможных комбинаций штампов (возможно, рекурсии), рассмотрим все возможное суммы, И выработайте, какое наименьшее количество штампов состоит в том, чтобы произвести каждую сумму. Есть множество комбинаций штампов, но намного меньше различных сумм.
В примере вы дали в комментарии, 10 марках подходят на конверт, и ни одна марка не имеет значения больше 100. Есть n^10 Комбинации штампов, где n Это количество деноминаций печать доступно. Но максимально возможная сумма из 10 марок составляет всего 1000. Создайте массив до 1001 и попытаться подумать о эффективном способе работы, для всех этих ценностей вместе, наименьшее количество штампов, необходимых для создания каждого. Твой ответ - тогда наименьший индекс, требующий 11 (или более) штампов, и вы можете ограничить каждую графику в 11 тоже.
«Эффективно» в этом случае в основном означает, что «избегайте повторения любой работы, к которой вам не нужно». Таким образом, вы захотите повторно использовать промежуточные результаты как можно больше.
Если это недостаточно подсказки, то либо (а) я ошибаюсь в подходе (в этом случае извините, я на самом деле не решил проблему самому, прежде чем ответить) или (б) обновить, чтобы сказать, как далеко у тебя есть вдоль этих строк.
Может быть, немного бесполезно просто дать «подсказки» о растворе DP, когда есть спекуляция, которые даже существует. Итак, вот Runnable Perl Code, реализующий фактический алгоритм DP:
#!/usr/bin/perl
my ($n, @stamps) = @ARGV;
my @_solved; # Will grow as necessary
# How many stamps are needed to represent a value of $v cents?
sub solve($) {
my ($v) = @_;
my $min = $n + 1;
return 0 if $v == 0;
foreach (@stamps) {
if ($v >= $_) {
my $try = $_solved[$v - $_] + 1;
$min = $try if $try < $min;
}
}
$_solved[$v] = $min;
return $min;
}
my $max = (sort { $a <=> $b } @stamps)[-1];
# Main loop
for (my $i = 0; $i <= $max * $n; ++$i) {
my $ans = solve($i);
if ($ans > $n) {
print "$i cannot be represented with <= $n stamps of values " . join(", ", @stamps) . ".\n";
last;
}
}
Обычно solve() потребует рекурсивный звонок, но потому что мы всегда пробуем значения в порядке 0, 1, 2, 3 ..., мы можем просто использовать @_solved Массив напрямую, чтобы получить ответ на более мелкие размеры проблем.
Это занимает 93 мс на моем ПК для решения случая для размеров штампов 1, 4, 12, 21 и размер конверта 1000. (Ответ 20967.) Компилированный язык будет даже быстрее.
import java.util.ArrayList;
import java.util.List;
/**
*
* @author Anandh
*
*/
public class MinimumStamp {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int stamps[]={90,30,24,15,12,10,5,3,2,1};
int stampAmount = 70;
List<Integer> stampList = minimumStamp(stamps, stampAmount);
System.out.println("Minimum no.of stamps required-->"+stampList.size());
System.out.println("Stamp List-->"+minimumStamp(stamps, stampAmount));
}
public static List<Integer> minimumStamp(int[] stamps, int totalStampAmount){
List<Integer> stampList = new ArrayList<Integer>();
int sumOfStamps = 0;
int remainingStampAmount = 0;
for (int currentStampAmount : stamps) {
remainingStampAmount = totalStampAmount-sumOfStamps;
if(remainingStampAmount%currentStampAmount == 0){
int howMany = remainingStampAmount / currentStampAmount;
while(howMany>0){
stampList.add(currentStampAmount);
howMany--;
}
break;
}else if(totalStampAmount == (sumOfStamps+currentStampAmount)){
stampList.add(currentStampAmount);
break;
}else if(totalStampAmount > (sumOfStamps+currentStampAmount) ){
int howMany = remainingStampAmount / currentStampAmount;
if(howMany>0){
while(howMany>0){
stampList.add(currentStampAmount);
sumOfStamps += currentStampAmount;
howMany--;
}
}else{
stampList.add(currentStampAmount);
sumOfStamps += currentStampAmount;
}
}
}
return stampList;
}
}
