java - 0/1背包算法的解释

Question

我的这个背包算法代码计算了应该使用的物品，以便以尽可能低的成本满足所有物品重量的最小重量总和。所以这是主要功能：

 public static void main(String[] args) {
        final int[] weights = {20,40,10,30}, costs = {5 ,20,2, 6};
        final int minWeight = 50;
        firstSolution(weights,costs,minWeight);
    }

这是方法：

public static void firstSolution(int[] weights, int[] costs, int minWeight){
        int maxWeight = 0;

        for(final int weight: weights){
            maxWeight += weight;
        }
        int[] solutions = new int[maxWeight+1];
        int[] minCost = new int[maxWeight + 1];

        for(int i = 1; i <= maxWeight; i++){
            minCost[i] = Integer.MAX_VALUE;
        }
        for(int i = 0; i < weights.length; i++){
            for(int j = maxWeight; j >= weights[i]; j--){
                if(minCost[j - weights[i]] != Integer.MAX_VALUE){
                    if (minCost[j - weights[i]] + costs[i] < minCost[j]) {
                        minCost[j] = minCost[j - weights[i]] + costs[i];
                        solutions[j] = i;
                    }
                }
            }
        }
        int answer = Integer.MAX_VALUE;

        for(int i = minWeight; i <= maxWeight; i++){
            answer = Math.min(answer, minCost[i]);
        }
        System.out.println(answer);
        while (minWeight > 0){
            System.out.println("Item no."+solutions[minWeight]+" will be used.");
            minWeight-=weights[solutions[minWeight]];
        }
    }

这段代码不是我的，我可以理解它在做什么，但不是很具体。不要讨厌我，因为我希望有人为我解释这段代码。我只是在看这个，知道一些基本的动态规划理论，但我就是无法理解。如果有人有 10 分钟的时间，请简单解释一下。谢谢。

标签： javaalgorithmoptimizationdynamic-programmingknapsack-problem