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

Question

我正在尝试从一组产品创建购物清单，其中 returned 购物清单应该针对成本进行优化并满足其他条件。

例如，假设我想根据产品的能量含量创建购物清单。当用户输入总金额时，returned 购物清单应尽量增加 kcal 含量，同时将总金额保持在或接近用户指定的金额。

到目前为止，我已经创建了产品集合，所有产品都存储为具有营养价值和价格等字段的对象。千卡值也作为成员变量存储在每个产品的对象中.

一开始我考虑循环遍历所有的产品组合，挑出那些超出价格区间的，然后return大卡含量最高的那个。但随着可用产品数量的增加，我认为这很快就会成为一个不可行的选择。

我现在想知道是否有算法可以解决这个问题，如果没有，有什么方法可以轻松实现吗？

Answer 1

我做了一些类似于动态规划的事情Wikipedia article on Dynamic Programming

下面的costs和values应该是长度相同的数组。可供选择的可能项目的长度。容量是您选择的项目的所有成本的最大总和。它 returns 一个相同长度的布尔数组，决定是否拿走该项目。

我们的想法是创建一个 table，其中包含子问题的解决方案，然后可用于解决更大的问题。子问题只是解决相同的问题，但列表较小，最初只有一个项目。 table 包含您可以从每个重量的前 i 件物品中获得的最大价值。当您将一个潜在项目添加到列表中时，您将其值添加到先前解决方案中允许的重量减去您添加的重量，并检查它是否比没有最后一项的先前解决方案更好。创建最后一行后，您可以通过检查最后一行中值的差异来判断要取哪些项目。

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

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

Creating optimal shopping list based on given conditions

java

optimization

combinatorics