Comment résoudre récursivement l'algorithme du sac à dos «classique»?

Qu'avez-vous essayer?

L'idée, compte tenu du problème que vous avez dit (qui précise que nous devons utiliser la récursivité) est simple: pour chaque élément que vous pouvez prendre, voir si c'est mieux de le prendre ou non. Donc, il n'existe que deux chemins possibles:

1. vous prenez l'élément
2. vous ne le prenez pas

Quand vous prenez l'article, vous le supprimez de votre liste et vous diminuez la capacité par le poids de l'objet.

Lorsque vous ne prenez pas le point, vous supprimez la si vous de la liste, mais vous ne diminuez pas la capacité.

Parfois, il contribue à l'impression de ce que les appels récursifs peut ressembler. Dans ce cas, il pourrait ressembler à ceci:

Calling 11 8 7 6 5  with cap: 20
+Calling 8 7 6 5  with cap: 20
|  Calling 7 6 5  with cap: 20
|    Calling 6 5  with cap: 20
|      Calling 5  with cap: 20
|      Result: 5
|      Calling 5  with cap: 14
|      Result: 5
|    Result: 11
|    Calling 6 5  with cap: 13
|      Calling 5  with cap: 13
|      Result: 5
|      Calling 5  with cap: 7
|      Result: 5
|    Result: 11
|  Result: 18
|  Calling 7 6 5  with cap: 12
|    Calling 6 5  with cap: 12
|      Calling 5  with cap: 12
|      Result: 5
|      Calling 5  with cap: 6
|      Result: 5
|    Result: 11
|    Calling 6 5  with cap: 5
|      Calling 5  with cap: 5
|      Result: 5
|    Result: 5
|  Result: 12
+Result: 20
Calling 8 7 6 5  with cap: 9
Calling 7 6 5  with cap: 9
Calling 6 5  with cap: 9
Calling 5  with cap: 9
Result: 5
Calling 5  with cap: 3
Result: 0
Result: 6
Calling 6 5  with cap: 2
Calling 5  with cap: 2
Result: 0
Result: 0
Result: 7
Calling 7 6 5  with cap: 1
Calling 6 5  with cap: 1
Calling 5  with cap: 1
Result: 0
Result: 0
Result: 0
Result: 8
Result: 20

Je l'ai fait sur le but de montrer l'appel à [8 7 6 5] avec une capacité de 20, ce qui donne un résultat de 20 (8 + 7 + 5).

Remarque que [8 7 6 5] est appelée deux fois: une fois avec une capacité de 20 (parce que nous n'avons pas pris 11) et une fois avec une capacité de 9 (parce que ne prendre 11).

De sorte que le chemin d'accès à la solution:

11 pas prises, l'appel à [8 7 6 5] avec une capacité de 20

8 prises, appelant [7 6 5] avec une capacité de 12 (20 - 8)

7 prises, appelant [6 5] avec une capacité de 5 (12 - 7)

6 pas prises, l'appel à [5] avec une capacité de 5

5 prises, nous sommes à zéro.

La méthode en Java peut s'adapter en très peu de lignes de code.

Puisque c'est évidemment des devoirs, je vais vous aider avec un squelette:

private int ukp( final int[] ar, final int cap ) {
if ( ar.length == 1 ) {
return ar[0] <= cap ? ar[0] : 0;
} else {
final int[] nar = new int[ar.length-1];
System.arraycopy(ar, 1, nar, 0, nar.length);
fint int item = ar[0];
if ( item < cap ) {
final int left = ...  //fill me: we're not taking the item
final int took = ...  //fill me: we're taking the item
return Math.max(took,left);
} else {
return ... //fill me: we're not taking the item
}
}
}

J'ai fait copier le tableau une nouvelle matrice, ce qui est moins efficace (mais de toute façon la récursivité n'est pas la voie à suivre ici si vous chercher de la performance), mais en plus "fonctionnelle".