Une solution complète au problème du sac à dos dans la programmation dynamique

Dans l'article précédent, nous avons appris ce qu'est un problème de programmation dynamique et ce qu'est un problème de sac à dos,Et analysé01Sac à dos,Si vous souhaitez lire l'article précédent, veuillez passer à–>Problème de sac à dos01Détails du sac à dos,Aujourd'hui, regardons le problème du sac à dos le problème complet du sac à dos.

Un.、Qu'est - ce qu'un problème de sac à dos complet？

Oui.nArticle (s),Le volume unitaire de chaque article est dev[i],Valeur:w[i].Une capacité existante estVSac à dos,Demandez comment choisir les articles à mettre dans votre sac à dos,Maximiser la valeur totale des articles dans le sac à dos.Chacun de ces objets est infini.
Sac à dos complet et01La différence entre les sacs à dos：

1. 01Le sac à dos ne peut être sélectionné qu'une seule fois ou pas lors du choix d'un article
2. Le sac à dos complet ne peut pas être sélectionné lors du choix d'un article , Vous pouvez aussi choisir une fois , Deux fois. ... Il n'y a pas de limite supérieure au nombre de sélections （ Tant que le sac à dos peut être posé ）

2.、Analyse des exemples

1. Titre：

2. Analyse：

2.1 Première étape：Déterminer les variables d'état（Fonctions）

La valeur maximale estNombre d'articlesiEtCapacité du sac à dosjFonction de.
Définir la fonctionf[i][j]Indique avantiLes articles ont une capacité dejLa valeur maximale du sac à dos.
La valeur maximale finale est le nombre d'articlesiDe0Croissance àn,Capacité du sac à dosjDe0Croissance àmHeuref[n][m]Valeur.

2.2 Deuxième étape：Déterminer l'équation de transfert d'état

Variables d'état：f[i][j]Indique avantiLes articles ont une capacité dejLa valeur maximale du sac à dos

La capacité actuelle estj,Nous devons tenir compte de laiArticle (s)Peut - on insérer？Oui Non？

1. Si la capacité actuelle du sac à dos j<v[i],Impossible de placer,Etf[i][j]=f[i-1][j]
2. Si la capacité actuelle du sac à dos j>=v[i], Peut être placé mais à un coût comparable
   2.1 SiiLes articles ne sont pas mis dans le sac à dos,Etf[i][j]=f[i-1][j]
   2.2 SiiMettez un article dans votre sac à dos,Etf[i][j]=f[i][j-v[i]]+w[i]

AvantiArticle (s),La capacité du sac à dos estj-v[i] Peut avoir été placé dans le iArticle (s),Capacité:j Il peut également être placé dans iArticle (s),Alors utilisezf[i][j-v[i]]Mise à jourf[i][j]

Équation de transfert d'état：

Peut être représenté comme ：

2.3 Conditions limites

Pour01 Le sac à dos dit que la limite est f[i][j]=0,C'est - à - direi=0Ouj=0Heuref[i][j]La valeur de0.

i=0Heure, Ça veut dire qu'il n'y a pas d'article dans le sac à dos , Il n'y a donc aucun moyen de parler de la valeur maximale du sac à dos ,Donc pour0;
j=0Heure, Indique que la capacité du sac à dos est 0, Il n'est donc pas possible de mettre l'article en ce moment , Donc la valeur maximale est aussi 0;

3. Représentation du processus

3.1 Code de base

    for(int i=1;i<=n;i++){
    //Articlesi
        for(int j=0;j<=m;j++)
            {
    
            if(j<v[i])
                f[i][j]=f[i-1][j];
             else
                f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
            }
     }
    cout<<f[n][m]<<endl;

3.2 Calcul manuel

3.3 Vérification du Code

3.4 Code complet

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main ()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           {
    
               if(j<v[i])
                    f[i][j]=f[i-1][j];
                else
                    f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
           }
    cout<<f[n][m]<<endl;
    return 0;
}

3.5 Optimisation

Optimiser la représentation bidimensionnelle en une dimension , Réduire l'utilisation de l'espace ,Avec un tableau unidimensionnelf[j]Enregistrer une seule ligne de données,JeanjCycle de séquence des valeurs,Mise à jour séquentiellef[j]
Code optimisé

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main ()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           {
    
               if(j<v[i])
                    f[j]=f[j];
                else
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
           }
    cout<<f[m]<<endl;
    return 0;
}

Parce quej C'est une boucle séquentielle ,f[j-v[i]]Avantf[j]Mise à jour,C'est - à - dire, Avec une nouvelle valeur f[j-v[i]]Pour mettre à jourf[j], C'est l'équivalent de iD'accord.f[j-v[i]]Mise à jour de la valeurf[j],Donc C'est vrai..