根據給定條件創建最佳購物清單

Question

我正在嘗試從產品集合中創建購物清單，其中返回的購物清單應優化成本以及滿足其他條件。

例如，假設我想根據產品的能量內容創建購物清單。當用戶輸入總金額時，返回的購物清單應該嘗試最大化大卡內容，同時將總金額保持在用戶指定金額或其附近。

我已經創建了產品集合，所有產品都存儲爲帶有保存營養價值和價格等字段的對象.kcal-value也存儲爲每個產品對象中的成員變量。

起初，我考慮循環產品的所有組合，將那些超出價格區間的產品進行整理，然後返回具有最高kcal內容的組合。但隨着可用產品數量的增加，這很快成爲我認爲不可行的選擇。

我現在想知道是否有算法來解決這個問題，如果沒有，有沒有什麼方法可以輕鬆實現呢？

Answer 1

我做編程Wikipedia article on Dynamic Programming

在下面的成本和價值應該是相同長度的陣列類似的東西與動態。可供選擇的項目的長度。容量是您選擇的項目所有成本的最大總和。它返回一組相同長度的布爾值數組，決定是否接受該項目。

這個想法是創建一個表的子問題的解決方案，然後可以用來解決更大的問題。子問題只是解決了同樣的問題，但列表較小，最初只有一個項目。該表包含了您可以獲得的最佳值，其中每個重量的第一個項目可達到最大值。當您將一個潛在物品添加到列表中時，您可以將其值添加到以前的解決方案中，以減少重量，並檢查是否比沒有最後一個物品的先前解決方案更好。一旦創建了最後一行，您可以通過檢查最後一行中的值存在差異來確定要採取哪些項目。

public boolean[] solve(int[] values, int[] costs, int capacity) { 
    boolean take[] = new boolean[values.length]; 
    int min_cost = Integer.MAX_VALUE; 
    for (int i = 0; i < values.length; i++) { 
     if (costs[i] < min_cost) { 
      min_cost = costs[i]; 
     } 
    } 
    int table[][] = new int[values.length][capacity + 1 - min_cost]; 
    for (int i = 0; i < values.length; i++) { 
     int v = values[i]; 
     int w = costs[i]; 
     for (int j = 0; j < capacity - min_cost + 1; j++) { 
      int prev_value = 0; 
      int new_value = 0; 
      if (i > 0) { 
       prev_value = table[i - 1][j]; 
       if (w <= j + min_cost) { 
        if (w <= j) { 
         new_value = table[i - 1][j - w] + v; 
        } else { 
         new_value = v; 
        } 
       } 
      } else if (w <= j + min_cost) { 
       new_value = v; 
      } 
      table[i][j] = Math.max(prev_value, new_value); 
     } 
    } 
    int index = capacity - min_cost; 
    for (int i = values.length - 1; i > 0 && index >= 0; i--) { 
     if (table[i][index] != table[i - 1][index]) { 
      take[i] = true; 
      index -= costs[i]; 
      if (index < 0) { 
       System.err.println("index = " + index); 
      } 
     } else { 
      take[i] = false; 
     } 
    } 
    take[0] = index >= 0 && table[0][index] != 0; 
    return take; 
}