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

Arrondir au petit matin de deux mètres de haut 2022-07-23 16:30:56 阅读数:51

unesolutioncomplteau

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:

Insérer la description de l'image ici

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 :
Insérer la description de l'image ici

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

Insérer la description de l'image ici

3.3 Vérification du Code

Insérer la description de l'image ici

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

Copyright:Cet article est[Arrondir au petit matin de deux mètres de haut]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2022/204/202207231229588777.html