Я хочу разработать алгоритм для проверки того, является ли мультимножество объединением суммы подмножества другого мультимножества, но я потерпел неудачу после нескольких часов самостоятельной борьбы.
Детали следующие:
Мультимножество A: положительное целочисленное множество
Мультимножество B: положительное целочисленное множество (меньше или равно A, позже вы узнаете, почему)
Функция алгоритма: проверьте, может ли для всех чисел в B соответствовать одно число или сумма чисел в A. Каждое число в A можно использовать только один раз, и все числа в A должны быть использованы. Все числа в B должны совпадать.
Пример, чтобы прояснить это: предположим, мультимножество A = {1, 3, 4, 4, 6}, B = {5, 6, 7}
Тогда алгоритм выдаст «ИСТИНА», так как 5 есть сумма 1 и 4, 6 равно 6, 7 есть сумма 3 и 4. При этом все числа в A используются и используются только один раз, а все числа в Б-ред проверено.
Но для A = {2, 6, 8}, B = {7, 9} алгоритм выдаст «ЛОЖЬ», хотя 2+6+8 = 7+9, но ни одно число в B не является суммой чисел в A .
Некоторые примечания:
1 Известные условия, сумма чисел в А равна сумме чисел в В.
2 Как показывают примеры, определенное число может встречаться несколько раз.
3 Каждое число в мультимножестве можно использовать только один раз, поэтому, если 3 используется в одном решении (чтобы получить 7), его нельзя использовать снова в другом решении. Число 4 встречается дважды, поэтому его можно использовать в двух решениях.
4 Возможны несколько решений для одного числа (например, 7 может быть 1 и 6 или это может быть 3 и 4), но некоторые (например, 7 могут быть 1 и 6) могут быть ошибочными в процессе проверки.
5 Мультимножество А небольшое, не более 30 элементов
Я стараюсь изо всех сил, но мое решение всегда не может охватить все условия мультимножества A и B. Я думал, что решение этого, по-видимому, выше моего понимания.
Так что мне очень нужна помощь ваших умных людей. Помогите мне, пожалуйста. Любой ответ будет принят с благодарностью!
