根据给定条件创建最佳购物清单

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; 
}