Проверьте, суммируются ли числа из нескольких массивов до заданных чисел

Это вариант 0-1 рюкзак проблема. Эта проблема является NP-трудной, поэтому нет надежды найти решение за полиномиальное время, но существует решение в псевдо-полином время, которое делает эту проблему довольно легкой (в мире сложных проблем).

Алгоритм работает следующим образом:

1. Начните с коллекции (например, набора), содержащей кортеж <0,0,0>,
2. Для каждого коробка <a',b',c'>: перебрать все кортежи <a,b,c> в коллекции и добавить <a+a',b+b',c+c'> в коллекцию, убедитесь, что дубликаты не добавляются. Не добавляйте кортежи, где один или несколько элементов имеют превышено соответствующее целевое значение.
3. Если данная коллекция содержит целевые значения после алгоритма, выведите «да», иначе «Нет».

4. Необязательно, но настоятельно рекомендуется нижний предел исключения: вы также можете выполнить предпросмотр и, например, исключить все значения, которые никогда не достигнут заданной цели (скажем, вы можете добавить 20 яблоки то все значения меньше чем 80 яблоки можно уничтожить).

   Концепция 1 (Нижняя граница): Так как вы добавляете значения кортежей вместе, вы теперь, если есть кортежи <a0,a1,a2> а также <b0,b1,b2> оставив, добавив их, можно максимально увеличить кортеж с <a0+b0,a1+b1,a2+b2>, Теперь скажите, что цель <t0,t1,t2> тогда вы можете безопасно удалить кортеж <q0,q1,q2> если q0+a0+b0 < t0 (обобщить на другие элементы кортежей), поскольку, даже если вы можете добавить последние кортежи, он никогда не достигнет требуемых значений. Таким образом, нижняя граница <t0-a0-b0,t1-a1-b1,t2-a2-b2>, Вы можете обобщить это для N кортежи.

Итак, сначала вы сложите все предоставленные кортежи вместе (для второго случая это <140,160,230>) и затем вычесть это из цели (результат, таким образом: <-40,-60,-130>). На каждой итерации нижняя граница увеличивается с этой коробкой, поэтому после первой итерации результат для второго примера равен (<-40+40,-60+70,-130+30> или же <0,10,-100>).

Однако сложность времени O (та ^ 3 тб ^ 3 тс ^ 3) с та, Т.Б. а также дц целевые значения.

Пример 1 (высокий уровень по двум заданным тестам):

ВХОД

100 100 100
3
10 10 40
10 30 10
10 60 50

Набор начинается с {<0,0,0>}после каждой итерации получаем:

1. {<0,0,0>};
2. {<0,0,0>,<10,10,40>};
3. {<0,0,0>,<10,10,40>,<10,30,10>,<20,40,50>}; а также
4. {<0,0,0>,<10,10,40>,<10,30,10>,<20,40,50>,<10,60,50>,<10,60,50>,<20,70,90>,<30,100,100>}Таким образом, провал.

С underbound-элиминирования:

1. {<0,0,0>}, нижняя граница <100-30,100-100,100-100>=<70,0,0> таким образом устранить <0,0,0>,
2. {} таким образом распечатать «Нет».

Пример 2

ВХОД

100 100 100
5
40 70 30
30 10 40
20 20 50
10 50 90
40 10 20

С нижний предел исключения:

1. {<0,0,0>} нижняя граница: <-40,-60,-130> таким образом, хорошо.
2. {<0,0,0>,<40,70,30>} нижняя граница: <0,10,-100> (Устранить <0,0,0> потому что вторые конфликты).
3. {<40,70,30>,<70,80,70>} нижняя граница: <30,20,-60> (без исключения).
4. {<40,70,30>,<70,80,70>,<60,90,80>,<90,100,120>} нижняя граница: <50,40,-10> (Устранить <40,70,30>) верхнее устранение <90,100,120>,
5. {<70,80,70>,<60,90,80>,<80,130,160>,<70,140,170>} нижняя граница: <60,90,80> (Устранить <70,80,70>) верхнее устранение <80,130,160> а также <70,140,170>,
6. {<60,90,80>,<100,100,100>} нижняя граница: <100,100,100> (Устранить <60,90,80>).
7. {<100,100,100>} таким образом «да».

Программа на Haskell

Я реализовал (не очень эффективную, но проверенную концепцию) программу на Haskell, которая добивается цели произвольной длины кортежа:

import qualified Data.Set as Set

tupleSize :: Int
tupleSize = 3

group :: Int -> [a] -> [[a]]
group _ [] = []
group n l = take n l : group n (drop n l)

empty :: Int -> Set.Set [Int]
empty n = Set.fromList [replicate n 0]

solve :: [Int] -> [[Int]] -> Bool
solve t qs = Set.member t $ mix t (lowerBound t qs) qs $ empty $ length t

lowerBound :: [Int] -> [[Int]] -> [Int]
lowerBound = foldl (zipWith (-))

lowerCheck :: [Int] -> [Int] -> Bool
lowerCheck l x = and $ zipWith (<=) l x

targetCheck :: [Int] -> [Int] -> Bool
targetCheck t x = and $ zipWith (>=) t x

takeout :: Int -> [a] -> [a]
takeout _ [] = []
takeout i (h:hs) | i == 0 = hs
| otherwise = h : takeout (i-1) hs

mix :: [Int] -> [Int] -> [[Int]] -> Set.Set [Int] -> Set.Set [Int]
mix _ _ [] s = s
mix t l (q:qs) s = mix t (zipWith(+) l q) qs $ Set.filter (lowerCheck l) $ Set.union s $ Set.filter (targetCheck t) $ Set.map (zipWith (+) q) s

reply :: Bool -> String
reply True = "yes"reply False = "no"
main = interact $ \x -> let tuples = group tupleSize $ takeout tupleSize $ map read (words x) in reply $ solve (head tuples) (tail tuples)

Вы можете скомпилировать запустить его, используя:

ghc file.hs
./file < input

Заключение: Хотя поведение в худшем случае может быть сложным, второй пример показывает, что проблему можно решить эффективно в некоторых случаях.