Алгоритм для нахождения подмножества в двух наборах целых чисел, суммы которых соответствуют
Можете ли вы попробовать обновленный код Возможно, проблема в контексте
public void displayDialogError() {
AlertDialog alertDialog = new AlertDialog.Builder(YourActivity.this);
alertDialog.setTitle("Alert");
alertDialog.setMessage("Alert message to be shown");
alertDialog.setButton(AlertDialog.BUTTON_NEUTRAL, "OK",
new DialogInterface.OnClickListener() {
public void onClick(DialogInterface dialog, int which) {
dialog.dismiss();
}
});
alertDialog.show();
}
4 ответа
То, что сказали другие, верно:
Эта проблема полна NP. Легкое сокращение к обычной сумме подмножества. Можно показать это путем отмечания, что подмножество суммы к подмножеству B (не оба пустеют), только если непустое подмножество объединения (-B) суммирует для обнуления.
Эта проблема только слабо полна NP, в котором это - многочлен в размере включенных чисел, но предугадано для экспоненциала в их логарифмах. Это означает, что проблема легче, чем "полный NP" моникер мог бы предложить.
Необходимо использовать динамическое программирование.
Таким образом, что я вношу в это обсуждение? Ну, код (в Perl):
@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
next unless exists $b{$m};
next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}
sub sums {
my( @a ) = @_;
my( $a, %a, %b );
%a = ( 0 => [] );
while( @a ) {
%b = %a;
$a = shift @a;
for my $m ( keys %a ) {
$b{$m+$a} = [@{$a{$m}},$a];
}
%a = %b;
}
return %a;
}
Это печатает
sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)
таким образом, особенно, существует больше чем одно решение, которое работает в Вашей исходной проблеме!
Править: Пользователь itzy правильно указал, что это решение было неверным, и хуже несколькими способами!! Я очень сожалею об этом, и я, надо надеяться, обратился к этим проблемам в новом коде выше. Тем не менее, существует все еще одна проблема, а именно, что за какую-то конкретную сумму подмножества, она только печатает одно из возможных решений. В отличие от предыдущих проблем, которые были прямыми ошибками, я классифицирую это как намеренное ограничение. Всего наилучшего и остерегайтесь ошибок!
Как проблема суммы подмножества, эта проблема слабо полна NP, таким образом, она имеет решение, которое работает в многочлене времени (M), где M является суммой всех чисел, появляющихся в проблемном экземпляре. Можно достигнуть этого с динамическим программированием. Для каждого набора можно генерировать все возможные суммы путем заполнения 2-мерной двоичной таблицы, где "верный" в (k, m) означает, что m суммы подмножества может быть достигнут путем выбора некоторых элементов сначала k элементы набора.
Вы заполняете его многократно - Вы устанавливаете (k, m) к "истинному", если (k-1, m) установлен на "истинный" (очевидно, если можно получить m от k-1 элементов, можно получить его от k элементов, не выбрав k-th), или если (k-1, m-d) установлен на "истинный", где d является значением k-th элемента в наборе (случай, где Вы выбираете k-th элемент).
Заполнение таблицы получает Вас все возможные суммы в последнем столбце (тот, представляющий полный набор). Сделайте это для обоих наборов и найдите общие суммы. Можно отследить в обратном порядке фактические подмножества, представляющие решения путем инвертирования процесса, который Вы раньше заполняли таблицы.
Большое спасибо за все быстрые ответы!
Решение для динамического программирования не действительно отличается от исчерпывающего approch, который мы имеем прямо сейчас, и я предполагаю, нужно ли нам оптимальное решение, мы действительно должны рассмотреть каждую возможную комбинацию, но время, которое требуется для генерации этого исчерпывающего списка сумм, являются слишком длинными.. Сделал быстрый тест и время, которое требуется для генерации всех возможных сумм для x числа элементов, очень быстро идут более чем 1 минута:
11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds
то, которое для бизнес-проблемы мы пытаемся решить, не действительно приемлемо.. Я собираюсь идти назад к исходной точке и видеть, должны ли мы действительно знать все решения, или можем мы просто сделать с одним (самое малочисленное/самое большое подмножество, например) вместо этого и надо надеяться который может помочь просто проблеме и заставить мой алгоритм работать к expectaion.
Но все равно спасибо!
сумма подмножества является Np-complete, и можно полиномиальным образом уменьшить проблему до него, таким образом, проблема полна NP также.