2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
1、équation de transition d'état：
Donc la formule récursive : dp[i][j] = max(dp[i - 1][j], dp[i - 1][j -weight[i]] + value[i]);
2. Initialisation
(1) À partir de la définition de dp[i][j], si la capacité du sac à dos j est 0, c'est-à-dire dp[i][0], quels que soient les éléments sélectionnés, la valeur totale du sac à dos doit être 0.
(2) Équation de transition d'état dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - poids[i]] + valeur[i]); vu que i est dérivé de i-1, il doit donc être initialisé lorsque i vaut 0.
dp[0][j], c'est-à-dire : i vaut 0, lors du stockage de l'élément numéro 0, la valeur maximale qu'un sac à dos de chaque capacité peut stocker.
Il est alors évident que lorsque j < poids[0], dp[0][j] doit être égal à 0, car la capacité du sac à dos est inférieure au poids de l'article numéroté 0.
Lorsque j >= poids[0], dp[0][j] doit être valeur[0], car la capacité du sac à dos est suffisante pour contenir l'article numéro 0.
- for (int j = 0 ; j < weight[0]; j++) {
- dp[0][j] = 0;
- }
- // 正序遍历
- for (int j = weight[0]; j <= bagweight; j++) {
- dp[0][j] = value[0];
- }
(3) Autre initialisation d'indice :
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - poids[i]] + valeur[i])
dp[1][1] = max(dp[0][1], dp[0][1-weight[i]] + value[i]) doit être à gauche et au-dessus,
Par conséquent, il doit avoir été initialisé et peut être défini sur n’importe quelle valeur. Pour plus de commodité, il est initialisé à 0 par défaut.
2. Unidimensionnel (tableau roulant)
1. Dans le tableau dp unidimensionnel, dp[j] signifie : un sac à dos d'une capacité de j peut transporter des objets d'une valeur maximale de dp[j]
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])2. Initialisation
(1) dp[0]=0, car la valeur maximale des objets transportés par un sac à dos d'une capacité de 0 est 0.
(2) Supposons que la valeur des éléments soit supérieure à 0,Afin de ne pas être écrasé par la valeur initiale, donc DPInitialisation du tableauQuand , ils sont tous initialement 0
3. Ordre de traversée
Traverser dans l'ordre inverse
Explication 1 : La valeur à la fin de la liste doit être déterminée en la comparant à la valeur précédente obtenue en parcourant le niveau précédent.
Explication 2 : Il n'y a qu'un seul sac à dos 01 pour chaque sac à dos. Le fait que ce sac soit placé ou non est lié au statut du sac précédent. Le tableau de gauche est une quantité décrivant le statut du sac précédent, et le numéro dessus. celui de droite est un statut en attente du sac actuel. Dans le code, le numéro de gauche est requis pour déterminer le tableau de droite, donc le numéro de gauche ne peut pas être détruit avant que le numéro de droite ne soit calculé.
Explication 3 : Pour deux dimensions, le résultat de chaque nouveau nombre dp que j'ai vient du haut et de la gauche ; en fait, ça devrait être comme ça en une dimension, mais en une dimension, si c'est toujours de gauche à droite, alors ma gauche actuelle Les chiffres ont été mis à jour ( Le côté gauche n’est plus le côté gauche « original » !Cela entraînera une double comptabilisation ), même si le dessus est toujours le dessus d'origine, le numéro obtenu est incorrect.Et si nous traversons de droite à gauche dans la couche du sac à dos (couche interne), alors l'élément de gauche sera toujoursIl ne sera pas écrasé par de nouvelles valeurs en raison de mon opération précédente., afin que la valeur correcte puisse être obtenue.
3. Demande
1. Étant donné un tableau non vide contenant uniquement des entiers positifs. Est-il possible de diviser ce tableau en deux sous-ensembles afin que la somme des éléments des deux sous-ensembles soit égale ?
Remarque : Les éléments de chaque tableau ne dépasseront pas 100 et la taille du tableau ne dépassera pas 200.
Exemple 1:
analyser:
L'article est moi,
Le poids est nums[i], la valeur est également nums[i] et le volume du sac à dos est sum/2.
Semblable au sac à dos 01
Équation de transition d'état :
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])- // 开始 01背包
- for(int i = 0; i < nums.size(); i++) {
- for(int j = target; j >= nums[i]; j--) {
- dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- }
- }
- // 集合中的元素正好可以凑成总和target
- if (dp[target] == target) return true;
2. Il y a un tas de pierres et le poids de chaque pierre est un entier positif.
À chaque tour, choisissez deux pierres et écrasez-les ensemble. Supposons que les poids des pierres soient respectivement x et y, et x <= y. Les résultats possibles du broyage sont alors les suivants :
Si x == y, alors les deux roches seront complètement écrasées ;
Si x != y, alors la pierre de poids x se brisera complètement et la pierre de poids y aura un nouveau poids de yx.
Au final, il ne restera au plus qu’une pierre. Renvoie le plus petit poids possible de cette pierre. S'il ne reste plus de pierres, renvoie 0.
Exemple:
analyser:
Essayez de diviser les pierres en deux tas de même poids, de sorte que la plus petite pierre restante après la collision
Divisez-le ensuite en deux tas de pierres. Le poids total d'un tas de pierres est dp[cible] et le poids total de l'autre tas est somme - dp[cible].
Lors du calcul de la cible, cible = somme / 2 car elle est arrondie à l'inférieur, donc somme - dp[cible] doit être supérieure ou égale à dp[cible]
Alors le poids minimum de la pierre restant après la collision est (somme - dp[cible]) - dp[cible]
- for (int i = 0; i < stones.length; i++) {
- //采用倒序
- for (int j = target; j >= stones[i]; j--) {
- dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
- }
- }
- //结果
- sum - 2 * dp[target];
cité de :Notes aléatoires de code
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
