动态规划问题

Question

我正在寻求一些有关动态规划问题的指导。我找不到任何相关信息来解决这种类型的问题。我知道如何使用动态规划解决两个序列的问题，即创建这些序列的矩阵。但我不知道如何将其应用于下面的问题...

如果我有一个集合A = {7,11,33,71,111} 和一个数B。那么C是A中的一个子集，包含从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

非常感谢您的帮助，我不知道在解决这类问题时该如何思考。我也找不到任何通用的方法，只有一些基因序列等方面的例子。

- Larssa

---

你是需要找到一个满足约束条件的C还是所有可能的C集合？ - Falaina

实际上，这似乎是可以使用子集和问题的多项式时间算法的情况。http://en.wikipedia.org/wiki/Subset_sum_problem - viksit

Answer 1

动态规划是一种广泛的解决方案类别，其中部分解决方案被保留在某些结构中，以便下一次迭代基于此进行构建，而不是一遍又一遍地重新计算中间结果。

如果我采用动态方法来解决这个特定问题，我可能会保留每个可计算的和的运行列表，以及用于计算该和的集合。

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

解决这个问题的方法不止一种。这是一种动态解决方案，效率不高，因为它需要构建一个2^(集合大小)成员的集合。但是，一般方法对应于动态编程被创建来解决的问题。

- Welbog

---

这种方法比暴力算法好得多吗？我有点想不是，但想知道你对这个想法有什么反馈。 - JB King

Answer 2

I think dynamic approach depend on B and number elements of A.

在这种情况下，我建议采用动态方法，其中B * A的元素数<= 1,000,000。

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[i-a[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";
}

- Vuong Long