算法 动态规划 01背包问题 Java实现

问题描述

有n件物品和一个最多能背重量为maxWeight的背包。第i件物品的重量是weights[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大？

问题分析

01背包问题是经典的动态规划问题。要想清楚这个问题，首先要想清楚dp数组以及状态转移方程。
该问题中的dp[j]的意义是：重量 j 能存放的最大价值(0 <= j <= maxWeight)。

看到这里大家应该会产生一个问题，明明只需要求出重量为maxWeight时能存放的最大价值，为什么要把所有重量能存放的最大价值都求出来呢？

为了回答这个问题，我们先来思考一下往背包里塞东西的过程。当我们要向背包里塞入物品 i 时，由于背包里已经有东西了，可能放不下物品 i 。那此时我们就要考虑是不塞物品 i 得到的价值更大？还是把已有的东西拿出来一些，再把物品 i 塞进去价值大？

在这一过程的思考中，我们就可以得到本题的状态转移方程：dp[j]=max(dp[j],dp[j-weights[i]]+values[i])。在max函数里，dp[j]对应着之前的情况，即放弃塞物品 i ；dp[j-weights[i]]+values[i]是选择塞物品 i 的情况，此时必须要为物品 i 的重量腾出一定的空间，故我们需要dp[j-weights[i]]的值，故要把所有重量能存放的最大价值都求出来。

所以我们需要尝试一个一个把物品塞到容量为0~maxWeght的背包里去，每次塞物品都要考虑是塞的价值大，还是不塞的价值大。

那么解决这个问题的流程就是：依次考虑物品 i （遍历物品），使用状态转移方程（dp[j]=max(dp[j],dp[j-weights[i]]+values[i])）依次求出重量 j 能存放的最大价值（dp[j])。

代码

Java

public class Bag {
    // 背包最大容量
    private int maxWeight;
    public Bag(int maxWeight){
        this.maxWeight=maxWeight;
    }
    public int fill(int[] weights,int[] values){
        // dp数组下标与背包容量相对应
        int[] dp=new int[this.maxWeight+1];
        // 依次遍历每个物品
        for (int i = 0; i < values.length; i++) {
            // 依次求出：加入考虑该物品后，背包各个容量的最大价值
            for (int j = dp.length-1 ; j > 0; j--) {
                if (j>=weights[i]){
                    // 状态转移方程
                    dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);
                }
            }
        }
        // 返回结果
        return dp[this.maxWeight];
    }

    // 测试
    public static void main(String[] args){
        int[] weights={1,3,4};
        int[] values={15,20,30};
        Bag bag=new Bag(6);
        System.out.println(bag.fill(weights, values));
    }
}