动态规划问题

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

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

Answer 1

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

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

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

解决这个问题的方法不止一种。这是一个动态的解决方案，效率不是很高，因为它需要构建一组2^(size of set)成员。但通用方法对应于创建动态编程所要解决的问题。

Answer 2

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

所以你必须选择的每一步：

使用aj，然后使用Fi，j=F[i-aj，j-1]

不使用aj然后使用Fi，j= Fi，j-1

如果存在FB、*=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";
}