Le temps de la Complexité de sac à Dos de la Programmation Dynamique de la solution

J'ai vu le récursive de la programmation dynamique solution à 0-1 problème de sac-à-Dos ici. Je memoized la solution et est venu avec le code suivant.

private static int knapsack(int i, int W, Map<Pair<Integer, Integer>>, Integer> cache)
{
 if (i < 0) {
    return 0;
 }
Pair<Integer, Integer> pair = new Pair<>(i,W);
if (cache.contains(pair)) {
  return cache.get(pair)
}
int result = -1;
if (weights[i] > W) {
    result = knapsack(i-1, W);
} else {
    result = Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
}
cache.put(pair, result);
return result;
}

Quelqu'un peut m'expliquer pourquoi la complexité temporelle O(nW) où n est le nombre d'éléments et W est la restriction sur le poids.

InformationsquelleAutor Lee | 2014-06-15
  1. 3

    C'est plus évident si vous pensez à ce que le tableau pourrait ressembler à un tableau de mise en œuvre de la DP. Il comporte des points sur un axe et max réalisables poids sur l'autre, avec une ligne par possible nombre entier de poids. Pour certains jeux de poids, la table doivent être remplis afin de trouver la meilleure réponse. Ces mêmes jeux de poids exigera Omega(nW) paires dans votre mémo de hachage, ergo depuis chaque entrée est une constante de temps de calcul, le même temps de calculer tous les. C'est un bon exercice pour réfléchir à la façon d'obtenir le coût des jeux de poids, donc je vais laisser cela à vous.

    • Merci un tas. Je comprends beaucoup mieux maintenant. Aussi, pourquoi le problème est considéré comme un problème NP-Difficile si vous pouvez arriver à un O(nW) solution?
    • NP-difficile est définie en termes d'exécution à l'égard de l'entrée de la longueur. W est de longueur plafond(log W). Donc O(W) est le même que O(2^# bits en W), qui est exponentielle du temps. Cette catégorie d'algorithmes est appelé "faiblement NP-difficile".
    InformationsquelleAutor Gene
  2. 4

    Ouais, c'est une des raisons pour lesquelles je n'aime pas la récursivité. Vous pouvez presque toujours réécrire un algorithme récursif dans un qui utilise uniquement des boucles et pas la récursivité. Voici ce que votre algorithme ressemble avec boucles for seulement:

    A[i,j]=0 for j=0, 1, ..., W

For i=1, 2, ..., n
    For j=0, 1, ..., W
        A[i,j]=max(A[i-1,j], A[i-1,j-weight[i]]+value[i] //or 0 if the index is invalid

Return A[n,W]

    Ici, il est évident que la complexité est O(nW). Je laisse à vous de comparer ce code avec le vôtre.

    • Merci Ali. J'semblent comme la récursivité pour une raison différente. Il est facilement applicable une fois que vous venez avec la relation récursive pour le type dynamique des problèmes de programmation.
    • En tout cas, j'espère que ma réponse vous aide un peu dans la compréhension de sa complexité.
    InformationsquelleAutor Ali
  3. 3

    Récursif algorithme de programmation dynamique peut être présenté par subproblem graphique.

    Subproblem graphique est constitué de sommets ressemblant à des non-chevauchement des sous-problèmes. Et les arêtes orientées dans le sommet de représenter les appels récursifs. Les arêtes représentent en fait la dépendance de la sous-problèmes.

    The runtime of the dynamic algorithm = (time to solve each subproblem)*(number of unique subproblems)

    Généralement, 

    the cost = (outdegree of each vertex)*(number of vertices)

    Pour sac-à-dos,

    Outdegree de chaque sommet est à plus de 2=O(1). C'est parce que dans chaque subproblem, nous essayons de le résoudre en au plus deux façons.

    Maintenant, si nous vérifions le sous-problèmes, on peut trouver un modèle,

    The subproblem `(n,W)` depends on `(n-1,W)` and `(n-1,W-w(n))`.

`(n-1,W)` depends on `(n-2,W)` and `(n-2,W-w(n-1))`
`(n-1,W-w(n))` depends on `(n-2,W-w(n))` and `(n-2,W-w(n)-w(n-1))`

    Noter que pour chacun des n éléments, le poids peut varier à la plupart des 1 to W.
    (On peut comparer cette extension du modèle de la dynamique de Fibonacci problème modèle avec une dimension supplémentaire.)

    Donc il y a au plus n*W unique sous-problèmes.

    Et que nous avons à résoudre chaque subproblem qu'une seule fois,

    Le temps d'exécution = O(1)O(nW) = O(n*M).

    • C'est une bonne explication!
    InformationsquelleAutor shuva
  4. -1
    import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Knapsack {
        double price;double kg;double pricePerKg;
Knapsack(double price,double kg, double pricePerKg){
    this.price=price;
    this.kg=kg;
    this.pricePerKg=pricePerKg;
}
public static List<Double> pricePerKg(List<Double> price,List<Double> kg){
    List<Double> pricePerKg = new ArrayList<Double>();
    for(int i=0;i<price.size();i++) {
        pricePerKg.add(price.get(i)/kg.get(i));
    }
    return pricePerKg;
}
public String toString() { return String.format("%s,%s,%s",price,kg,pricePerKg); }
    public static void main(String[] args) {
    List<Knapsack> list = new ArrayList<Knapsack>();
    double W=50;
    List<Double> price = new ArrayList<Double>();
    price.add(60.00);
    price.add(120.00);
    price.add(100.00);
    price.add(1000.00);
    ArrayList<Double> kg = new ArrayList<Double>();
    kg.add(10.00);
    kg.add(30.00);
    kg.add(20.00);
    kg.add(100.00);
    List<Double> pricePerKg =pricePerKg(price,kg);
    double weightCarry=0,currentWeight=0;
    double sum=0;
    for(int i=0;i<pricePerKg.size();i++) {
        list.add(new Knapsack(price.get(i),kg.get(i),pricePerKg.get(i)));
    }
    Collections.sort(list,new Comparator<Knapsack>() {
        @Override
        public int compare(Knapsack o1, Knapsack o2) {          
             return o1.pricePerKg > o2.pricePerKg ? -1 : o1.pricePerKg == o2.pricePerKg ? 0 : 1;
        }
    });
    System.out.println(list.toString().replaceAll(",", "\n"));
    for(int i=0;i<list.size();i++) {
        Knapsack li=list.get(i);
        weightCarry+=Double.valueOf(li.toString().split(",")[1]);
            if(weightCarry<W) {
                sum+=Double.valueOf(li.toString().split(",")[1])*Double.valueOf(li.toString().split(",")[2]);
              currentWeight=weightCarry;
            }
            else {
                sum+=(W-currentWeight)*Double.valueOf(li.toString().split(",")[2]);
            break;
            }
    }
    System.out.println("Fractional knapsack="+sum);
}
}

    Complexité temporelle est près de O(nlogn)

    InformationsquelleAutor Virendra kumar