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