Приведенные n проверок, каждое из произвольного (целочисленного) денежного значения, решают, можно ли разделить чеки на две части, имеющие одинаковое денежное значение.Придумайте полиномиальный алгоритм
Я не понимаю, как это решить. Есть ли алгоритм для решения этого в полиномиальное время или это NP-Complete?
Да, это проблема с NP. Это вариация the subset sum problem.
Удивительное спасибо! Я был так озадачен этим. Любопытно, что если бы у меня было N проверок двух разных значений. Например, значение X и значение Y. Тогда любой алгоритм для этого будет NP полным? – mocode9
Для двух разных значений вы можете решить простое диофантово уравнение. В общем случае существуют псевдополиномиальные алгоритмы, использующие динамическое программирование. – MBo
Вы ошибаетесь, это можно сделать с полиномиальной сложностью, используя динамическое программирование. –
Фактически вы можете решить эту проблему в O (n * sum/2) с помощью динамического программирования, сначала суммируйте все проверки в сумму вариабеля, затем вы можете выполнить dp на значениях проверок (либо взять его, либо оставить или принять это) и проверить в конце, если эта сумма равна s/2.
Возможно, этот вопрос лучше размещен в [программировании головоломки] (http://codegolf.stackexchange.com/) или [puzzling] (http://puzzling.stackexchange.com/) – yaitloutou
@yaitloutou Я думаю, что вопрос здесь гораздо больше по теме, чем в головоломке или программировании. В лучшем случае, возможно, он должен быть отправлен на сайт cs.stackexchange.com. – user31264
@ user31264 благодарит вас за разъяснение – yaitloutou