Dynamic programming issues

Question

I am looking for a few pointers to a dynamic programming problem. I can not find relevant information on how to solve this problem. The only problem I know how to solve using dynamic programming is when I have two sequences and create a matrix from these sequences. But I do not see how I can apply this to the next problem ...

If I have a set A = {7,11,33,71,111} and a number B. Then C, which is a subset of A, contains elements from A, which builds the sum of B.

Example:

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

Thanks for any help here, I just don’t know how to think when solving such problems. I also cannot find a general method, only some examples of gene sequences and the like.

Answer 1

Dynamic programming is a wide category of solutions in which a partial solution is stored in some structure for subsequent subsequent iteration, instead of recounting intermediate results again and again.

If I were to take a dynamic approach to this particular problem, I would probably keep a list of all the calculated amounts from the previous step, as well as the set used to calculate this amount.

, , {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.

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

, , :

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