Problèmes de programmation dynamique

Question

Je cherche des pointeurs sur un problème de programmation dynamique. Je ne trouve aucune information pertinente sur la façon de résoudre ce genre de problème. Le seul genre de problème que je sais résoudre en utilisant la programmation dynamique est quand j'ai deux séquences et crée une matrice de ces séquences. Mais je ne vois pas comment je peux l'appliquer au problème suivant ...

Si j'ai un ensemble A = {7,11,33,71,111} et un nombre B. Puis C qui est un sous-ensemble de A, contient les éléments de A qui construit la somme B.

Exemple:

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 

Thankful pour toute aide ici, je ne sais pas comment penser pour résoudre ce genre de problèmes. Je ne trouve pas non plus de méthode générale, seulement quelques exemples sur des séquences de gènes et des trucs comme ça.

Answer 1

La programmation dynamique est une vaste catégorie de solutions dans lesquelles une solution partielle est conservée dans une structure pour l'itération suivante au lieu d'avoir à recalculer les résultats intermédiaires encore et encore. Si je devais adopter une approche dynamique à ce problème particulier, je garderais probablement une liste courante de toutes les sommes calculables de l'étape précédente, ainsi que l'ensemble utilisé pour calculer cette somme.

Ainsi, par exemple la première itération mon jeu de travail contiendrait {null, 7}, je voudrais ajouter 11 à tout ce qui a mis ainsi que l'ensemble lui-même (nous allons faire semblant que null+11=11 pour l'instant). Maintenant, mon jeu de travail contient {null, 7, 11, 18}. Pour chaque valeur de l'ensemble, je voudrais garder une trace de la façon dont j'ai obtenu ce résultat: donc 7 correspond à l'ensemble original {7} et 18 à l'original {7,11}. L'itération se termine lorsque A) la valeur cible est générée ou B) l'ensemble d'origine est épuisé sans trouver la valeur. Vous pouvez optimiser le cas négatif avec un ensemble ordonné, mais je vais vous laisser le soin de vous le dire.

Il existe plusieurs façons d'aborder ce problème. C'est une solution dynamique, et ce n'est pas très efficace car il faut construire un ensemble de membres 2^(size of set). Mais l'approche générale correspond à ce que la programmation dynamique a été créée pour résoudre.

Answer 2

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

Je suggère une approche dynamique dans ce cas avec l'élément numéro 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 

Ainsi, chaque étape, vous devez choise:

utiliser un [j ] alors F [i, j] = F [ia [j], j-1]

ne font pas l'utilisateur a [j] alors F [i, j] = F [i, j-1]

Ensuite, si elle existe un F [B, *] = 1, vous pouvez construire B.

Bellow est un exemple de code:

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