请教一算法！

会说话的哑巴 · 发表于 2004-6-16 04:42:33

<

>92年的一道题，已知18种氨基酸，另给一分子量X(X<=1000)，要求分解此分子量，列出所有可能的氨基酸组合。
这题其实就是用18个已知数来组成X,求出可行解的。
本人想到了用嵌套循环的方法，可是太复杂了的，不知有没其他高效算法可以解决这个问题呢？
希望给出详细的解答步骤！！！谢谢！！！！

xcy · 发表于 2004-6-27 06:08:50

<

>[em07]我有一种算法，就是定义一个数组，然后对这个数组进行操作。我是新手，我说的不能登大雅之堂的[em35]

xcy · 发表于 2004-6-27 06:11:37

一起讨论一下嘛

会说话的哑巴 · 发表于 2004-6-27 19:55:08

<

>斑竹呢？？高手呢？？帮忙回答下！！！<

>顶！

itmwk · 发表于 2004-6-27 22:14:18

除了回溯法,我也没想到什么更好的办法,不过用回溯时用上栈/递归做起来应该也还行,有空我把程序给你发上来

itmwk · 发表于 2004-7-1 21:09:31

<

>粗略写了一下,代码如下

IK04Ob4h.rar (1.29 KB, 下载次数: 0)

[此贴子已经被作者于2004-7-1 13:44:43编辑过]

SummerRain · 发表于 2005-8-28 01:04:27

<

>典型的一道DP问题。
<

>定义 f(m, k): 表示用1..k 这前k中氨基酸组成分子量为m的组法。
<

>f(m, k) = f(m - value[k]*1, k-1) + f(m - value[k]*2, k-1)+..
f(m - value[k]*i, k-1);
注意记录状态，别重复就行了。至于生成组合方案，只需要记录上述转移的可行状态。

		自动登录	找回密码
密码			注-册-帐-号