大家抓紧着啊，下周最后一周了 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

大家抓紧着啊，下周最后一周了 (转载)

大家抓紧着啊，下周最后一周了 (转载)# Joke - 肚皮舞运动

t*h2010-04-23 07:04

1 楼

Write a function that takes in an array of integers and outputs the number
of ways you can combine those integers to obtain a sum of 15.
Example: for [10,5,3,2], output = 2.
我只想到用递归生成所有结果
如果等于15就把计数器加一
careercup上说可以用DP来做但是我想不到
请问这个问题用DP怎么做？

w*s2010-04-23 07:04

2 楼

【以下文字转载自 NextGeneration 讨论区】
发信人: whiteclouds (/ 参考消息 /), 信区: NextGeneration
标题: 疫苗立法性命攸关!!!!
发信站: BBS 未名空间站 (Sat Mar 12 12:55:15 2011, 美东)

z*t2010-04-23 07:04

3 楼

【以下文字转载自 Chicago 讨论区】
发信人: FBI (杯具，餐具，洗具，三具一体。), 信区: Chicago
标题: 大家抓紧着啊，下周最后一周了
发信站: BBS 未名空间站 (Fri Apr 23 16:55:36 2010, 美东)
papadeux周三周四晚上小龙虾和oyster特价.
最近几乎每周都去。昨天晚上去晚了，龙虾就卖完了，然后就一口气吃了三打oyster,
把旁边桌子的老黑都给吓傻了。

D*h2010-04-23 07:04

4 楼

for a given sum and array a[1],a[2]....a[n]
f(sum, i, n) = f(sum-a[i], i+1,n)+f(sum,i+1,n)
where f(sum, i,n) is the # of combination from a[i] to the end a[n].

【在 t******h 的大作中提到】

: Write a function that takes in an array of integers and outputs the number
: of ways you can combine those integers to obtain a sum of 15.
: Example: for [10,5,3,2], output = 2.
: 我只想到用递归生成所有结果
: 如果等于15就把计数器加一
: careercup上说可以用DP来做但是我想不到
: 请问这个问题用DP怎么做？

c*e2010-04-23 07:04

5 楼

又去读了你pie的评论，也没看懂。。。忍住没打枪？？很黄？

【在 z***t 的大作中提到】

: 【以下文字转载自 Chicago 讨论区】
: 发信人: FBI (杯具，餐具，洗具，三具一体。), 信区: Chicago
: 标题: 大家抓紧着啊，下周最后一周了
: 发信站: BBS 未名空间站 (Fri Apr 23 16:55:36 2010, 美东)
: papadeux周三周四晚上小龙虾和oyster特价.
: 最近几乎每周都去。昨天晚上去晚了，龙虾就卖完了，然后就一口气吃了三打oyster,
: 把旁边桌子的老黑都给吓傻了。

m*g2010-04-23 07:04

6 楼

coin 变种？

b*h2010-04-23 07:04

7 楼

这个问题跟经典的knapsack问题很像。从两个维度上可以减小问题的规模；一个是sum
的大小，另一个是数组的大小。对于给定的sum和数组，可以考虑数组里的每一个元素a
[i]。要么a[i]被选中，要么不被选中。如果a[i]被选中,那么答案就是剩下的数组元素
有多少种组合能生成sum-a[i]。反之，答案就是剩下的数组元素有多少种组合能生成
sum。

c*n2010-04-23 07:04

8 楼

recursion ---> memoization ---> DP
is rather simple, it's almost a mechanical translation process
your recursion version for this problem is:
let a[] be the array of possible integers
number_of_ways(N, a[]) = sum( number_of_ways(N- a[i], a[] - a[i]) )
while base case is number_of_ways(0, anything) = 1
and number_of_ways(n , anything) = 0 where n < 0
这个题如果像上面限制每个integer 只能用一次，用DP 不太好表达，如果可以重复
使用，就很
简单：
for n = 1 to 15:
for (i=1 to MAX_NUMBER_OF_AVAILABLE_INTEGERS ) :
if ( n - a[i] > 0 ) :
ways[n] += ways[n-a[i]]

【在 t******h 的大作中提到】

B*n2010-04-23 07:04

9 楼

假设数组是a[i], i = 1..n
如果某些数字的和为sum，有两种情况，或者第n个数字被选，或者第n个数字没有被选
count(n, sum) = count (n-1, sum) + count(n-1, sum-a[n]);
只要用一个二维数组来保存dp状态就可以了

【在 t******h 的大作中提到】