cpp算法 给出正整数n，得出一个1到n的数组，将其分成两部分，使这两部分的和相同，问情况数量。

Question

如给出整数7.得出数组1234567
167 2345
257 1346
347 1256
。。。。
共xx种情况

Answer 1

给定一个数组，长度为偶数，将数组分成长度相等两部分，使两部分和最接近

先介绍01背包，然后解决长度可以不相等的情况，最后解决该问题

问题0: 01背包问题---k件商品，每件都有重量wi以及价格vi,给定一个袋子容量为W,求袋子中存放商品价值最大的取货方案

令f(k,w)为袋里可用容量为w时，取前k件商品的最大总价值

若已知f(k-1,w)，求出f(k,w)：第k件商品重量为wk,价格vk

若wk>w,则袋子容量不够，不能取第k件 f(k,w) = f(k-1, w)

若wk<w,则袋子容量足够，若取第k件，有总价值f(k-1,w-wk)+vk ，若不取则f(k-1, w) 有： f(k,w) = max{f(k-1,w-wk)+vk,f(k-1,w)}

递归方式解决：

def bag(k, w, v, W):
if k==-1:
return 0
if w[k]>W:
return bag(k-1, w, v, W)
else:
return max(bag(k-1,w,v,W), bag(k-1,w,v,W-w[k])+v[k])
临界条件k==-1时，不论背包可用容量如何，没有商品可以取，直接返回0；当k=0时第一件商品，若w[0]>W，则返回bag（-1，W）=0

若w[0]<w则返回max(bag(-1,W),bag(-1,W-w0)+v[0])