Exemple de code pour résoudre le problème du sac à dos en Java

Cet article présente principalement l'exemple de code de résolution de problèmes de sac à dos Java, qui implique deux types de sacs à dos : 01 et le sac à dos complet. Les idées et les méthodes de mise en œuvre des deux sacs à dos sont décrites respectivement, ce qui a une certaine valeur de référence. Les amis dans le besoin peuvent en apprendre davantage.

Le problème du sac à dos concerne principalement un sac à dos d'une capacité donnée et un certain nombre d'articles d'une certaine valeur et d'un certain poids. Comment choisir les articles à mettre dans le sac à dos pour maximiser la valeur des articles. Il est divisé en sac à dos 01 et sac à dos illimité. Ici, nous discutons principalement du sac à dos 01, ce qui signifie que chaque élément peut être placé au maximum. Le sac à dos infini peut être transformé en sac à dos 01.

Parlons d'abord de l'idée principale de l'algorithme et utilisons la programmation dynamique pour le résoudre. Chaque fois que le ième élément est parcouru, il est déterminé si l'élément doit être mis dans le sac à dos en fonction de w[i] et v[i]. Autrement dit, pour n articles donnés, soit v[i] et w[i] respectivement la valeur et le poids du i-ème article, et C la capacité du sac à dos. Soit v[i][j] représenter la valeur maximale des i premiers éléments pouvant être chargés dans un sac à dos de capacité j. On a alors les résultats suivants :

(1), v[i][0]=v[0][j]=0;
(2), v[i][ j]=v[i-1][j] Quand w[i]>j
(3), v[i][j]=max{v[i-1][j],v[i -1][j-w[i]]+v[i]} Quand j>=w[i]

D'accord, notre algorithme est basé sur ces trois formules de conclusion.

1.01 sac à dos :

1. >

Sortie :

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i个物品能装入容量为j的背包中的最大价值 
    int[][] path = new int[n+1][m+1]; 
    //初始化第一列和第一行 
    for(int i=0;i<f.length;i++){ 
      f[i][0] = 0; 
    } 
    for(int i=0;i<f[0].length;i++){ 
      f[0][i] = 0; 
    } 
    //通过公式迭代计算 
    for(int i=1;i<f.length;i++){ 
      for(int j=1;j<f[0].length;j++){ 
        if(weight[i-1]>j) 
          f[i][j] = f[i-1][j]; 
        else{ 
          if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){ 
            f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; 
            path[i][j] = 1; 
          }else{ 
            f[i][j] = f[i-1][j]; 
          } 
          //f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); 
        } 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      for(int j=0;j<f[0].length;j++){ 
        System.out.print(f[i][j]+" "); 
      } 
      System.out.println(); 
    } 
    int i=f.length-1; 
    int j=f[0].length-1; 
    while(i>0&&j>0){ 
      if(path[i][j] == 1){ 
        System.out.print("第"+i+"个物品装入 "); 
        j -= weight[i-1]; 
      } 
      i--; 
    } 
  } 
}

La complexité temporelle et spatiale de la méthode ci-dessus est à la fois O(N *V ), la complexité temporelle ne peut fondamentalement plus être optimisée, mais la complexité spatiale peut être optimisée à O(V).

0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 4 4 4 4 4 4 4 4 4 4 
0 0 0 4 4 4 4 4 8 8 8 8 8 
0 0 3 4 4 7 7 7 8 8 11 11 11 
0 0 3 4 4 7 7 7 8 9 11 12 12 
0 0 3 4 4 7 7 7 8 10 11 12 12 
第4个物品装入 第3个物品装入 第1个物品装入

Considérez d'abord comment mettre en œuvre l'idée de base mentionnée ci-dessus. Il doit y avoir une boucle principale i=1..N, et à chaque fois le tableau bidimensionnel f[i][0..V. ] est calculé toutes les valeurs. Ainsi, si un seul tableau f[0..V] est utilisé, peut-on garantir qu'après la fin de la i-ème boucle, f[v] représente l'état f[i][v] que nous avons défini ? f[i][v] est dérivé récursivement des deux sous-problèmes f[i-1][v] et f[i-1][v-c[i]]. (c'est-à-dire que lorsque f[v] est poussé dans la i-ème boucle principale), les valeurs de f[i-1][v] et f[i-1][v-c[i]] être obtenu ? En fait, cela nous oblige à pousser f[v] dans l'ordre v=V..0 dans chaque boucle principale, afin de garantir que lorsque f[v] est poussé, f[v-c[i]] sauvegarde l'état f Valeur [i -1][v-c[i]].

Le pseudo code est le suivant :

où f[v]=max{f[v],f[v-c[i] ]} Cette phrase est exactement équivalente à notre équation de transfert f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}, car maintenant f[v-c [ i]] est équivalent à l'original f[i-1][v-c[i]]. Si l'ordre cyclique de v passe de l'ordre inverse ci-dessus à l'ordre, alors il devient f[i][v]. Il peut être déduit de f[i][v-c[i]], ce qui est incompatible avec la signification. de cette question, mais c'en est une autre. Un problème important du sac à dos P02 est la solution la plus simple, il est donc très nécessaire d'apprendre à résoudre le problème du sac à dos 01 en utilisant uniquement des tableaux unidimensionnels.

for i=1..N
  for v=V..0
    f[v]=max{f[v],f[v-c[i]]+w[i]};

Parmi les questions que nous avons vues sur la recherche de la solution optimale au problème du sac à dos, il existe en fait deux manières différentes de la poser. Certaines questions nécessitent la solution optimale lorsque le sac à dos est rempli avec précision, tandis que d'autres questions n'exigent pas que le sac à dos soit rempli. Une méthode de mise en œuvre qui distingue ces deux questions consiste à faire une différence lors de l'initialisation.

Si c'est la première question qui nécessite que le sac à dos soit rempli exactement, alors lors de l'initialisation sauf que f[0] vaut 0, les autres f[1..V] sont réglés sur -∞, afin que l'on puisse garantir que le f[N] final est une solution optimale qui remplit simplement le sac à dos.

S'il n'est pas nécessaire de remplir le sac à dos, mais que vous souhaitez seulement que le prix soit aussi grand que possible, tous les f[0..V] doivent être mis à 0 lors de l'initialisation.

Pourquoi ? Cela peut être compris de cette façon : le tableau f initialisé est en fait l'état légal dans lequel aucun objet ne peut être mis dans le sac à dos. Si le sac à dos doit être exactement plein, alors seul le sac à dos d'une capacité de 0 peut être "exactement rempli" avec rien d'une valeur de 0. Il n'y a pas de solution légale pour les sacs à dos d'autres capacités et ils sont dans un état indéfini , et leurs valeurs sont toutes. Cela devrait être -∞. Si le sac à dos n'a pas besoin d'être rempli, alors un sac à dos de n'importe quelle capacité a une solution légale de "ne rien emballer". La valeur de cette solution est 0, donc les valeurs de l'état initial sont toutes 0.

2. Méthode de tableau unidimensionnel (pas besoin de remplir)

Sortie

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=0;i<f.length;i++){   //不必装满则初始化为0 
      f[i] = 0; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

0 0 3 4 4 7 7 7 8 10 11 12 12 
最大价值为12

3. Méthode de tableau unidimensionnel (doit être rempli)

Sortie

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=1;i<f.length;i++){   //必装满则f[0]=0,f[1...m]都初始化为无穷小 
      f[i] = Integer.MIN_VALUE; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

0 -2147483648 3 4 3 7 6 7 8 10 11 12 11 
最大价值为11

2. Sac à dos complet
Il existe N types de articles et une capacité du sac à dos de V a un nombre illimité de pièces de chaque article disponible. Le coût du ième article est c[i] et la valeur est w[i]. Recherchez quels articles peuvent être emballés dans un sac à dos afin que le coût total de ces articles ne dépasse pas la capacité du sac à dos et que la somme de leurs valeurs soit maximale.

Mais nous avons un meilleur algorithme O(VN).

Algorithme O(VN)
Cet algorithme utilise un tableau unidimensionnel, regardons le pseudo-code d'abord :

Vous constaterez que ce pseudocode n'est différent du pseudocode de P01 que dans l'ordre des boucles de v.

for i=1..N
  for v=0..V
    f[v]=max{f[v],f[v-cost]+weight}

Sortie

public class test{ 
   public static void main(String[] args){ 
      int[] weight = {3,4,6,2,5}; 
      int[] val = {6,8,7,5,9}; 
      int maxw = 10; 
      int[] f = new int[maxw+1]; 
      for(int i=0;i<f.length;i++){ 
        f[i] = 0; 
      } 
      for(int i=0;i<val.length;i++){ 
        for(int j=weight[i];j<f.length;j++){ 
          f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
        } 
      } 
      System.out.println(f[maxw]); 
   } 
  }

25

总结

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!