3

我正在寻找有关动态编程问题的一些指示。我找不到任何有关如何解决此类问题的相关信息。我知道如何使用动态编程解决的唯一一种问题是当我有两个序列并创建这些序列的矩阵时。但我不知道如何将其应用于以下问题......

如果我有一个集合 A = {7,11,33,71,111} 和一个数字 B。那么作为 A 的子集的 C 包含来自 A 的元素，这些元素构成总和 B。

例子：

A = {7,11,33,71,111}
If B = 18, then C = {7,11} (because 7+11 = 18)

If B = 3, then there is no solution

感谢这里的任何帮助，我只是不知道在解决这类问题时如何思考。我也找不到任何通用方法，只有一些关于基因序列的例子和类似的东西。

4

2 回答 2

5

动态编程是一类广泛的解决方案，其中部分解决方案保存在某种结构中以供下一次迭代构建，而不是让它一遍又一遍地重新计算中间结果。

如果我要对这个特定问题采取动态方法，我可能会保留一个运行列表，其中包含上一步可计算的每个总和，以及用于计算该总和的集合。

因此，例如，我的工作集将包含的第一次迭代{null, 7}，然后我将添加11到该集中的所有内容以及集本身（让我们暂时假设null+11=11）。现在我的工作集将包含{null, 7, 11, 18}. 对于集合中的每个值，我会跟踪我是如何得到该结果的：因此7映射到原始集合{7}并18映射到原始集合{7,11}。当 A) 生成目标值或 B) 原始集合用尽而未找到该值时，迭代将结束。您可以使用有序集优化否定情况，但我会留给您解决。

解决这个问题的方法不止一种。这是一个动态的解决方案，它不是很有效，因为它需要构建一组2^(size of set)成员。但一般方法对应于创建动态规划来解决的问题。

于 2009-09-29T16:20:06.703 回答
0 
I think dynamic approach depend on B and number elements of A.

在这种情况下，我建议采用动态方法，使用 A <= 1.000.000 的 B*number 元素

Use call F[i,j] is true if use can use from A[1] to A[j] to build i and false otherwise

因此，您必须选择的每一步：

使用 a[j] 然后 F[i,j]=F[ia[j],j-1]

不要用户 a[j] 然后 F[i,j] = F[i,j-1]

然后，如果存在 F[B,*]=1 ，则可以构建 B。

下面是示例代码：

#include<stdio.h>
#include<iostream>

using namespace std;

int f[1000][1000], a[1000], B,n;
// f[i][j] = 1 => can build i when using A[1]..a[j], 0 otherwisw
int tmax(int a, int b){
    if (a>b) return a;
    return b;
}
void DP(){
    f[0][0] = 1;
    for (int i=1;i<=B;i++)
        for (int j=1;j<=n;j++)
        {
            f[i][j] = f[i][j-1];
            if (a[j]<=i) 
                f[i][j] = tmax(f[i-a[j]][j-1], f[i][j]);
        }
}


int main(){
    cin >> n >> B;
    for (int i=1;i<=n;i++) cin >>a[i];
    DP();
    bool ok = false;
    for (int i=1;i<=n;i++){
        if (f[B][i]==1) {
            cout<<"YES";
            ok = true;
            break;
        }   
    }

    if (!ok) cout <<"NO";
}
于 2015-08-18T10:39:14.000 回答