问题描述
有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));}
}
