当前位置:网站首页>The most detailed Backpack issues!!!

The most detailed Backpack issues!!!

2022-04-23 16:06:00 Zheyu Harry

Nous savons que,Le problème du sac à dos est un problème de programmation dynamique très classique,Cet article résume et analyse plusieurs types de problèmes de sac à dos:

 

Selon Baidu Encyclopedia,On peut voir le problème du sac à dos(Knapsack problem)Est une combinaison optimiséeNPQuestion complète.Le problème peut être décrit comme:Compte tenu d'un groupe d'articles,Chaque article a son propre poids et son propre prix,Dans la limite du poids total limité,Comment choisir,Pour que le prix total de l'article soit le plus élevé.Le nom de la question provient de la façon de choisir l'article le plus approprié à placer dans un sac à dos donné.Des problèmes similaires se posent souvent dans les entreprises、Mathématiques combinatoires,Théorie de la complexité computationnelle、Dans des domaines tels que la cryptographie et les mathématiques appliquées.Le problème du sac à dos peut également être décrit commeQuestions décisives,C'est - à - dire que le poids total ne dépasse pasWSur la base de, La valeur totale peut - elle atteindre V?C'est dans1978AnnéeMerkleEtHellmanProposé par.

 

En général, Nous pouvons les diviser en plusieurs types :

·01Problème de sac à dos

·Problème de sac à dos complet

·Problème de sac à dos multiple

·Problème de sac à dos combiné

 

On va régler ça un par un , La première chose que nous voyons d'abord est la base 01Problème de sac à dos:

01 Le sac à dos nous dit qu'il y a nArticle (s), Chaque article que vous choisissez ou non , Choisissez au plus une fois ;

 

Considérons d'abord les algorithmes simples , C'est comme ça que la violence s'épuise , Mais il s'est avéré évident qu'il y avait 2^nPossibilité de semences,C'est inacceptable.  .  Et si nous utilisons la programmation dynamique ici, nous pouvons effectivement réduire la complexité temporelle à O(NV), Ici, nous extrayons l'objet et l'état de l'espace de problème , Donc nous définissons l'état comme :

dp[i][j] Indique seulement avant i Envisager de mettre ou non des articles ,Le volume total ne doit pas dépasserjHeure, La plus grande valeur possible .

On va commencer par tout dpInitialiser comme0, Ensuite, nous avons examiné si nous devions charger iArticle (s),Il y a deux possibilités::

1.Ne pas charger leiArticle (s),Etdp[i][j] = dp[i-1][j];

2.Chargement de laiDans le cas d'un article,dp[i][j] = dp[i-1][j - v[i] ] + w[i];

C'estdp[i][j] Dans l'étude de i Deux types d'articles C'est possible., Nous pouvons donc obtenir l'équation de transfert d'état suivante :

dp[i][j] = max(dp[i-1][j] , dp[i-1][j - v[i] ] + w[i] );

 

Et,On peut trouver,dp[i][j]Quant àdp[i-1][0~j-1]Concernant, Ainsi, nous pouvons utiliser l'optimisation spatiale couramment utilisée dans la programmation dynamique (Faire défiler le tableau,C'est - à - dire SupprimerdpLa première dimension de),Et puis à laiSous - couche,Sidp[j] Non mis à jour ,C'estdp[i-1][j], Si elle a été mise à jour dp[i][j]C'est, Donc nous pouvons trouver qu'après avoir optimisé l'espace, , Nous ne pouvons pas couvrir le cycle de la couche supérieure , Donc énumérer les volumes j Ne peut être énuméré qu'à l'envers , Il s'agit d'éviter de mettre à jour les valeurs de la même dimension avec les valeurs mises à jour. ;

 

L'idée centrale de la programmation dynamique est d'éviter le double comptage. ,Noi La valeur maximale de l'article chargé et non chargé peut être obtenue par i-1 La valeur maximale d'un article détermine , Et l'énumération violente ignore ce fait !

 

Code:

#include<bits/stdc++.h>
#define maxn 1010

using namespace std;
int v[maxn],w[maxn];
int f[maxn];
int n,m;

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 = m;j>=v[i];j--)
f[j] = max(f[j - v[i]] + w[i], f[j]);
cout << f[m] << '\n';
return 0;
}

 

Et puis..., Nous passons ensuite au deuxième type de sac à dos. Problème de sac à dos complet

Problème de sac à dos complet et 01 Le problème du sac à dos est différent , Le problème du sac à dos complet i Les articles ont une réserve infinie , Prenez autant que vous voulez ;

Nous avons deux idées analytiques communes , D'abord, on peut parler à 01 Tout comme le problème du sac à dos, définissez d'abord l'état. :

dp[i][j] Indique seulement avant i Envisager de mettre ou non des articles ,Le volume total ne doit pas dépasserjHeure, La plus grande valeur possible .

 

Mais nous pensons ici à la i Voulez - vous ajouter un article Quand, On n'a pas à penser dp[i-1][j - v[i] ] , C'est un transfert versdp[i][j - v[i] ]Moyenne, C'est - à - dire qu'après l'adhésion de i Les articles peuvent - ils être ajoutés après iArticle (s);

 

On pourrait aussi écrire:

dp[i][j] = max(dp[i-1][j] , dp[i-1][j - v[i] ] + w[i] , dp[i-1][j - 2*v[i] ] + 2*w[i] ……,dp[i-1][j - k*v[i] ] + k*w[i] )

dp[i][j - v[i] ] = max(dp[i-1][j - v[i] ]  , dp[i-1][j - 2*v[i] ] + w[i] ……,dp[i-1][j - k*v[i] ] + (k-1)*w[i] )

On peut voir que la partie rouge est juste à côté. w[i], Donc nous pouvons écrire l'équation de transition d'état :

dp[i][j] = min(dp[i][j - v[i] ] + w[i] , dp[i-1][j]);

 

C'est la première façon d'analyser , Ensuite, la deuxième méthode d'analyse , C'est - à - dire directement au - dessus de k Listez - les un par un pour obtenir la valeur maximale ,C'est plus compliqué., Il n'y a donc pas d'autres détails !

 

Code:

#include<bits/stdc++.h>
#define maxn 1010

using namespace std;
int v[maxn],w[maxn];
int f[maxn];

int main()
{
int n,m;
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 = v[i];j<=m;j++)
f[j] = max(f[j],f[j - v[i]] + w[i]);
cout << f[m] << '\n';

return 0;
}

 

L'optimisation de l'espace est également possible ici , C'est la même méthode , Mais nous avons découvert que parce que nous avons des équations de transition d'état ,Oui.dp[i][j - v[i] ], Donc nous pouvons mettre à jour les valeurs de la même dimension avec les valeurs mises à jour , Donc ici, nous n'avons pas besoin d'une énumération inversée, nous pouvons simplement faire une énumération circulaire vers l'avant ;

 

La question suivante s'appelle Problème de sac à dos multiple, C'est à cause de la i Un objet n'est pas comme 01 Un maximum d'un article dans le sac à dos , Et il n'y a pas autant de choix que dans un sac à dos complet , Peut également être basé sur la complexité des données , Il y a deux façons d'analyser :

·················À suivre···············

版权声明
本文为[Zheyu Harry]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231604455417.html