动态规划问题

Question

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

如果我有一个集合 A = {7,11,33,71,111} 和一个数字 B。那么 C 是 A 的子集，包含示例

：

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

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

使用 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";
}