最少费用购物问题java代码

最小费用购物问题通常是一个经典的动态规划问题，也称为背包问题的一个变种。目标是在满足物品重量限制的情况下，选择一组商品使得总费用最低。以下是使用 Java 编程解决这个问题的一个基本思路：

class Item {
    int weight;
    int price;

    // 构造函数
    public Item(int w, int p) {
        this.weight = w;
        this.price = p;
    }
}

public class MinimumCostShopping {
    private static int minCost(int[] weights, int[] prices, int maxWeight, Item[] items) {
        int n = items.length;
        int[][] dp = new int[n + 1][maxWeight + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= maxWeight; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = 0;
                else if (weights[i - 1] <= j)
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + prices[i - 1]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[n][maxWeight];
    }

    public static void main(String[] args) {
        Item[] items = {new Item(5, 10), new Item(6, 11), new Item(7, 12)};
        int[] weights = {2, 3, 4};
        int[] prices = {3, 4, 5};
        int maxWeight = 8;
        System.out.println("Minimum cost to buy all items within the weight limit is: " + minCost(weights, prices, maxWeight, items));
    }
}

在这个代码中，`minCost` 函数通过填充动态规划数组 `dp` 来计算最小费用。它遍历每个商品，如果当前商品能放入背包（即重量不超过剩余容量），则比较不取这个商品和取这个商品的成本，然后取成本较小的结果。