2012-10-17 7 views
3

Я должен выполнить следующую вариацию проблемы с рюкзаком. Каждый предмет для ранца имеет приоритет и вес. Теперь я указываю вес X. Я должен знать, вычислить наименьший набор элементов, сумма веса которых не меньше X и имеет самый низкий приоритет. Каждый элемент может быть выбран только один раз. Пример:Рюкзак - наименьший приоритет, минимальный вес

KnapsackItem a = new KnapsackItem("a", 1000, 0.1); 
    KnapsackItem b = new KnapsackItem("b", 1000, 0.01); 
    KnapsackItem c = new KnapsackItem("c", 1000, 0.01); 

    Knapsack sack = new Knapsack(1900); 
    sack.addItem(a); 
    sack.addItem(b); 
    sack.addItem(c); 

    for (KnapsackItem item : sack.compute()) { 
     System.out.println(item); 
    } 

Это должно возвращать b, c.

Мое решение возвращает b, a. Я не знаю почему. Отработанные часы отладки, но я просто не понимаю. Возможно, кто-то может взглянуть или опубликовать решение этой проблемы как код.

public class Knapsack { 
/** 
* The sum of the priorities. For example "prisoSum.get(2) returns 5" means, 
* that element 2 returns a sum priority of 5. 
*/ 
private HashMap<Integer, Double> prioSum = new HashMap<Integer, Double>(); 

/** 
* List of items. 
*/ 
private ArrayList<KnapsackItem> items; 

/** 
* Minimum weight. The sum of the weights of the items in the item list must 
* at least be equal to this value. 
*/ 
private int minWeight; 

/** 
* Constructor. 
* 
* @param minWeight 
*   the minimum weight. 
*/ 
public Knapsack(final int minWeight) { 
    this.items = new ArrayList<KnapsackItem>(); 
    this.minWeight = minWeight; 
} 

/** 
* Computes the items to select. 
* 
* @return list of items to select. 
*/ 
public final ArrayList<KnapsackItem> compute() { 
    ArrayList<KnapsackItem> ret = new ArrayList<KnapsackItem>(); 
    int weightLeft = this.minWeight; 
    KnapsackItem item; 

    while (weightLeft > 0) { 
     ArrayList<KnapsackItem> diff = getDifference(this.items, ret); 
     if (diff.size() == 0) { 
      break; 
     } 

     item = computeBestItemForMinVal(diff, 
       weightLeft); 

     ret.add(item); 
     weightLeft -= item.getWeight(); 
    } 

    return ret; 
} 

/** 
* Gets the best item to select for a given weight. 
* 
* @param list 
*   List of items to select form 
* @param minVal 
*   given weight 
* @return best item from list for given weight 
*/ 
private KnapsackItem computeBestItemForMinVal(
     final ArrayList<KnapsackItem> list, final int minVal) { 
    int[] best = new int[minVal + 1]; 
    for (int w = 0; w <= minVal; w++) { 
     for (int i = 0; i < list.size(); i++) { 
      KnapsackItem curIt = list.get(i); 

      // Current priority inclusive all antecessors 
      double curVal = 0; 
      if (prioSum.get(w - curIt.getWeight()) != null) { 
       curVal = prioSum.get(w - curIt.getWeight()) 
         + curIt.getPriority(); 
      } else { 
       curVal = 0 + curIt.getPriority(); 
      } 
      if (prioSum.get(w) == null) { 
       prioSum.put(w, curVal); 
       best[w] = i; 
      } else if (prioSum.get(w) > curVal) { 
       prioSum.put(w, curVal); 
       best[w] = i; 
      } 
     } 
    } 
    return list.get(best[minVal]); 
} 

/** 
* Computes the difference between two given list of Knapsack items and 
* returns it. 
* 
* @param main 
*   first list 
* @param sub 
*   second list 
* @return difference 
*/ 
private ArrayList<KnapsackItem> getDifference(
     final ArrayList<KnapsackItem> main, 
     final ArrayList<KnapsackItem> sub) { 
    ArrayList<KnapsackItem> ret = new ArrayList<KnapsackItem>(); 

    for (int m = 0; m < main.size(); m++) { 

     boolean found = false; 
     for (int s = 0; s < sub.size(); s++) { 
      if (main.get(m).getName() == sub.get(s).getName()) { 
       found = true; 
       break; 
      } 
     } 

     if (!found) { 
      ret.add(main.get(m)); 
     } 
    } 

    return ret; 
} 

} 
+1

Когда вы шагаете через код, в котором линия она делает что-то другое, что вы ожидаете, и что это? –

+1

Это домашнее задание? Я знаю, что тег домашней работы устарел, но все же хорошо сказать, когда это происходит, потому что тогда люди попытаются написать свои ответы таким образом, чтобы вы узнали больше всего об этом. – Philipp

ответ

0

Я нашел свою ошибку. Я должен добавить prioSum.clear(); для вычисленияBestItemForMinVal(). Таким образом, данные предыдущих вызовов удаляются. Я также запустить для цикла для веса в настоящее время на 1, а не на 0:

private KnapsackItem computeBestItemForMinVal(
     final ArrayList<KnapsackItem> list, final int minVal) { 
    int[] best = new int[minVal + 1]; 
    prioSum.clear(); 
    for (int w = 1; w <= minVal; w++) { 
...