请教一道算法题

有N（c1,c2,c3...cn）个硬币，每个硬币的数额是（v1,v2,...vn），要把这些硬币分成2份，需要每份的数额加起来都大于k。求问有几种可行的分配。
是一道dynamic programming的题，求助。


补充内容 (2018-12-6 00:37):

Input：The first line of the input consists of the number N and K such that 1 ≤ N ≤ 100 and 1 ≤ K ≤ 105. The next line contains N numbers: v1, v2, . . . , v...

补充内容 (2018-12-6 00:38):
that indicate the values of the coins c1,c2,...,cN respectively. For each vi, we have 1 ≤ vi ≤ 109 for i ∈ [1...N].

补充内容 (2018-12-6 00:57):
time complexity要求 O(N·K)， space complexity要求 O(N+K)

瞎逼逼几句:
试试转化问题为其中一堆个数小于 k 的方案数?
然后就成了比较裸的01背包计数题了,方案数为 ans
时间复杂度就是01背包时间复杂度,然后空间复杂度可以用滚动数组,
结果等于 2^(n-1) - ans ?
细节可能有问题

scidylanpno 发表于 2018-12-7 21:04
瞎逼逼几句:
试试转化问题为其中一堆个数小于 k 的方案数?
然后就成了比较裸的01背包计数题了,方案数为 a ...

谢谢 应该是这个思路，因为这个帖子审核了太久所以期间在stackoverflow上找到答案了