0 - 1 problème de sac à dos (1)

Catalogue des articles de la série

0-1Problème de sac à dos（Un.）

Conseils：Après avoir écrit l'article,Le répertoire peut être généré automatiquement,Comment générer un document d'aide à droite

---

Préface

Conseils：Voici le texte de cet article,Les exemples suivants sont à titre de référence

Un.、0-1Quel est le problème avec le sac à dos?？

Le problème avec le sac à dos est「Planification dynamique」Une catégorie très classique de problèmes,Le problème du sac à dos appartient essentiellement à l'optimisation combinatoire「NP Question complète」.Parce qu'il y a trop de combinaisons,Il n'est donc pas possible de résoudre le problème par la méthode de l'épuisement,C'est pour ça que「Problème de sac à dos」Sera utilisé「Planification dynamique」Pour résoudre les causes profondes.Voici un exemple simple0-1Problème de sac à dos.

2.、Diviser l'égalité et le Sous - ensemble（Leetcode 416Moyenne）

1.Description du problème

Pour toi Ne contient que des entiers positifs De Non vide Tableau nums .Décidez si vous pouvez diviser le tableau en deux sous - ensembles,Rendre les éléments des deux sous - ensembles égaux.

2.Aperçu de l'algorithme

2.1 0-1L'idée de base du problème du sac à dos

0-1 Le problème du sac à dos est essentiellement un problème de programmation dynamique , L'essence du problème de programmation dynamique est de rechercher les changements numériques causés par les changements dans l'état suivant et l'état précédent ,C'est - à - dire l'équation de transfert d'état,dp[i][j]Etdp[i-1][j]La relation entre.
0-1 Le problème du sac à dos est en fait le même problème ,dp[i][j]=max(dp[i-1][j],dp[i-1][jv[i]]+wight[i]), Ça veut dire traverser un objet à la fois , Il y a deux options ：Prendre ou ne pas prendre, Le volume du sac à dos sera réduit , .Si vous ne récupérez pas, gardez l'état original .

2.2 Analyse des problèmes spécifiques

Cette question peut être convertie en question de sac à dos , Processus de modélisation des problèmes ： Quelle est la taille du sac à dos 、 Quantité et valeur des articles 、 Forme des résultats

1.Nombre d'articles：numsDesize
2.Valeur de l'article：numsLa valeur correspondante
3. Le volume du sac à dos ： C'est le point difficile de la forme générale du sac à dos , Il n'y a aucune indication sur la valeur maximale du sac à dos , Il faut déformer le problème ： Rendre les éléments des deux sous - ensembles égaux ==》 Somme de chaque sous - ensemble == Tous les éléments et 1/2, Donc le volume du sac à dos est aussi évident que tous les éléments et 1/2.
4. Forme des résultats ： Il faut d'abord analyser ce que nous avons calculé , Calculer la valeur obtenue comme étant la valeur maximale qui peut être obtenue comme étant le volume du sac à dos , La question est de savoir si c'est égal. , La forme du résultat peut donc être convertie en ： Le sac à dos peut - il être rempli , C'est - à - dire si la valeur maximale est égale au volume du sac à dos .
Cet article ne présente que la solution la plus primitive au problème du sac à dos , C'est aussi la forme originale , .Plusieurs variantes et Optimisations sont faites autour de ce sujet dans les prochains articles

2.4 Affichage du Code：

class Solution {
    
public:
    bool canPartition(vector<int>& nums) {
    
        int N=nums.size();
        int sum=0;
        for(int i=0;i<N;i++)
        {
    
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        int C=sum/2;
        vector<vector<int>>dp(N,vector<int>(C+1,0));
        // D'abord.「 Considérez le premier article 」Situation
        for (int i = 0; i <= C; i++) {
    
            dp[0][i] = i>=nums[0] ? nums[0] : 0;
        }
        // Retraitement「 Considérez le reste 」Situation
        for (int i = 1; i < N; i++) {
    
            for (int j = 0; j < C + 1; j++) {
    
                //  Ne choisissez pas cet article 
                int n = dp[i - 1][j];
                //  Sélectionnez cet article ,Prémisse「Capacité restante」Supérieur ou égal à「Volume de l'article」
                int y =j>nums[i]? dp[i - 1][j-nums[i]]+nums[i]:0; 
                dp[i][j] =max(n,y);
            }
        }
        return dp[N-1][C]==C;
}
};

Résumé

Conseils：Voici un résumé de l'article：
Aujourd'hui, l'explication principale「Qu'est - ce qu'un problème de sac à dos」、「 Quelle est la nature du problème du sac à dos 」Et「 Pourquoi la programmation dynamique est - elle nécessaire pour résoudre le problème du sac à dos et la difficulté de résoudre les problèmes de routine et de déformation du sac à dos ,Parmi eux「01Sac à dos」 Le problème est au cœur des nombreux problèmes de sac à dos .