Я думаю, что это проблема NP, потому что я мог бы уменьшить проблему с рюкзаком до этого, и согласно этой статье проблема с рюкзаком является NP-полной.действительно, в задаче о ранце есть алгоритм псевдополиномиального времени в значении размера рюкзака, но в нем нет алгоритма полиномиального времени в размере входных данных.
уменьшение проблемы рюкзака до проблемыВы указали:
- описание моей проблемы с рюкзаком:
1 - предположим, что у вас есть два рюкзака, размер которых оба c.
2 - у вас есть n предметов с объемамиv1, v2, .. vn.
3 - вы хотите положить все эти n предметов в свои рюкзаки.
- сводя эту проблему к вашей проблеме:
1- построить граф с (n + 1) вершинами.
2- вершина i соединена с вершиной (i + 1) двумя ребрами.один со стоимостью vi (объем i-го элемента) и один со стоимостью ноль.
3 - вы хотите найти два непересекающихся ребра пути от вершины 1 до вершины (n + 1) с верхней границей, равнойРазмер рюкзака.
, поэтому, если бы вы могли решить свою задачу в полиноме, проблема в рюкзаке была решена в полиноме, и вы доказали P = NP.: D
Конечно, согласно приведенному выше описанию, вы можете решить свою проблему за полиномиальное время в граничном весе графа, но это алгоритм псевдополиномиального времени, а не реальный, в отличие от алгоритма Surballe.извините за плохой английский.