检查来自多个数组的数字是否总和为给定数字

Question

我正在尝试做这道题：

Given three integers: GA, GB, and GC(which represent apples, oranges, and bananas respectively) & N lines each consisting of three integers: A, B, and C, which represent the amount of apples, oranges, and bananas in that food, respectively.

Check if it's possible to use only certain cartons such that the total apples, oranges, and bananas sum up to GA, Gb and GC respectively. For each available carton, we can only choose to buy it or not to buy it. He can't buy a certain carton more than once, and he can't buy a fractional amount of a carton.

Sample Test Case

IN
100 100 100
3
10 10 40
10 30 10
10 60 50
OUT

no

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

yes

对于这个问题，我已经编写了一些代码，但只出现了分段错误和一些错误。另外，我的算法很糟糕。我所做的是找到 apples 数组的所有子集，使得它们的总和为 GA，然后我检查这些集合中是否有橙子和香蕉要添加到 GB 和 GC。但是这个想法很慢而且很难编码...

我相信这在某种程度上是背包问题的变体，可以以更好的复杂度解决（至少比 O(2^N)[我当前的复杂度] ;P 好）。那么，解决这个问题的更好算法是什么，另外，请参阅我当前的代码 PasteBin（我没有将代码放在 Whosebug 上，因为它有缺陷，而且，我相信我必须开始从零开始...)

Answer 1

这是 0-1 背包问题 的变体。这个问题是NP-hard的，所以在多项式时间内找到解的希望不大，但是在伪多项式时间内存在一个解，这使得这个问题很容易（在复杂问题的世界）。

算法的工作原理如下：

从包含元组 <0,0,0>.
For each carton <a',b',c'>:遍历集合中的所有元组<a,b,c>并添加<a+a',b+b',c+c'> 到集合中，确保 不添加重复项 。不要添加一个或多个元素超过相应目标值的元组。
如果给定集合包含算法后的目标值，打印"yes"，否则"no" .
可选但强烈建议 下限消除：您还可以执行前瞻，例如消除所有值永远不会再达到给定的目标（假设你最多可以添加 20 个苹果，那么所有小于 80 个苹果的值都可以被淘汰）。

Concept 1 (Lowerbound): Since you add values of tuples together, you now that if there are tuples <a0,a1,a2> and <b0,b1,b2> left, adding these will at most increase a tuple with <a0+b0,a1+b1,a2+b2>. Now say the target is <t0,t1,t2> then you can safely eliminate a tuple <q0,q1,q2> if q0+a0+b0 < t0 (generalize to other tuple elements), since even if you can add the last tuples, it will never reach the required values. The lower bound is thus <t0-a0-b0,t1-a1-b1,t2-a2-b2>. You can generalize this for n tuples.

因此，首先将所有提供的元组加在一起（对于第二个实例，即 <140,160,230>），然后从目标中减去它（因此结果为：<-40,-60,-130>）。每次迭代，下界都会随着纸箱的增加而增加，因此在第一次迭代之后，第二个示例的结果是 (<-40+40,-60+70,-130+30> or <0,10,-100>).

但是时间复杂度是 O(ta^3 tb^3 tc^3) with ta, tb 和 tc 目标值。

示例 1（两个给定测试用例的高级）：

输入

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

集合从{<0,0,0>}开始，每次迭代后我们得到：

{<0,0,0>};
{<0,0,0>,<10,10,40>};
{<0,0,0>,<10,10,40>,<10,30,10>,<20,40,50>};和
{<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-elimination:

{<0,0,0>},下界<100-30,100-100,100-100>=<70,0,0>从而消除<0,0,0>.
{} 因此打印 "no".

示例 2

输入

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

有下限消除:

{<0,0,0>} 下限：<-40,-60,-130> 这样就可以了。
{<0,0,0>,<40,70,30>}下界：<0,10,-100>（去掉<0,0,0>因为第二个冲突）。
{<40,70,30>,<70,80,70>}下界：<30,20,-60>（无消元）。
{<40,70,30>,<70,80,70>,<60,90,80>,<90,100,120>}下界：<50,40,-10>（消去<40,70,30>）上界消去<90,100,120>.
{<70,80,70>,<60,90,80>,<80,130,160>,<70,140,170>}下界：<60,90,80>（消去<70,80,70>）上界消去<80,130,160>和<70,140,170>.
{<60,90,80>,<100,100,100>}下界：<100,100,100>（消去<60,90,80>）.
{<100,100,100>} 因此 "yes".

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

Conclusion: Although the worst-case behavior can be hard, the second example shows that the problem can be solve efficiently for some cases.

Answer 2

分段错误完全是你的问题。

Knapsack 是 NP-complete，这个也是（假设输入 A、B、C 始终相同，并且 Ga = A 的总和的一半）。我认为这里没有人要求您解决 NP 完全问题。

显然，您不会检查所有集合，而只会检查总和 A <= 100、总和 B <= 100、总和 C <=100 的集合。

Answer 3

与此相同的情况 question。

此问题是 Facebook Hackercup 资格赛目前进行中的第 2 道题（将于世界标准时间 1 月 12 日凌晨 12 点结束）。

在这里询问活动编程竞赛问题的解决方案是不公平的。

检查来自多个数组的数字是否总和为给定数字

Check if numbers from multiple arrays sum up to given numbers

c++

arrays

algorithm

knapsack-problem