2019独角兽企业重金招聘Python工程师标准>>> 
笔者参加美团在线笔试的时候，遇到了一道动态规划的相关题目，很遗憾当时的笔者非常稚嫩，对算法简直一窍不通，于是抱着求学的态度，打算入门动态规划的时候，发现了这个经典的动态规划（Dynamic Programming，DP）入门题--0/1背包问题，看完大神们的解答思路，简直顶礼膜拜，于是打算自己手动实现下，致敬大佬们。特此，摘记。
所谓的0/1表示的就是装入背包的物品只有两种状态（装入与不装入）。 OK，废话不多说，上题：
题目：
条件：
* 一个背包，最大容量12Kg
* 5个物品，分别的重量为1 , 3 , 2 , 6 , 2（单位都是Kg）,分别的价值为2 , 5 , 3 , 10 , 4（这个单位任意）
问题：
* 求背包最多能装下多少价值的物品？
OK，谈下解题思路：
- 确认子问题和状态 01背包问题需要求解的就是，为了体积V的背包中物体总价值最大化，N件物品中第i件应该放入背包中吗？（其中每个物品最多只能放一件） 为此，我们定义一个二维数组，其中每个元素代表一个状态，即前i个物体中若干个放入体积为V背包中最大价值。数组为：f[N][V]，其中fij表示前i件中若干个物品放入体积为j的背包中的最大价值。
- 初始状态 初始状态为f[0][0−V]和f[0−N][0]都为0，前者表示前0个物品（也就是空物品）无论装入多大的包中总价值都为0，后者表示体积为0的背包啥价值的物品都装不进去。
- 转移函数
if (背包体积j小于物品i的体积)
f[i][j] = f[i-1][j] //背包装不下第i个物体，目前只能靠前i-1个物体装包
else
f[i][j] = max(f[i-1][j], f[i-1][j-Vi] + Wi)
最后一句的意思就是根据“为了体积V的背包中物体总价值最大化，N件物品中第i件应该放入背包中吗？”转化而来的。Vi表示第i件物体的体积，Wi表示第i件物品的价值。这样f[i-1][j]代表的就是不将这件物品放入背包，而f[i-1][j-Vi] + Wi则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。
OK,上笔者自己撸的代码：
package package_0_1;
/**
* 0/1 背包问题
* @author xiao
*
*/
public class Package01 {
// 背包的最大重量
public static int package_weight_max = 12;
// 一共有几种物品
public static int Total_Item = 5;
// 每种物品的价值
public static int[] values= {0 , 2 , 5 , 3 , 10 , 4};
// 每种物品的重量
public static int[] Items_Weight = {0 , 1 , 3 , 2 , 6 , 2};
/* 一个二维数组，用来表示从前i个物品里
* 选出最合适的装进载重量为j背包中，使
* 得背包里的价值最大。i∈Items j∈{0-package_weight_max}
* dp[i][j] 单位是 (价值)
*/
public static int dp[][] = new int[Total_Item+1][package_weight_max+1];
/**
* 初始化dp二维数组
*/
public static void initialize_dp() {
for(int[] i : dp) {
for(int j :i) {
j=0;
}
}
}
/**
* DP 计算递推矩阵(求出每个局部最优解，将其保存进二维数组，方便递推)
*/
public static int DPMethod() {
initialize_dp();
// 构造二维数组
for(int i = 1;i<=Total_Item;i++) {
for(int j = 1;j<=package_weight_max;j++) {
/* 如果背包容量小于物品的重量，则不放入此物品，
* 将放入上一物品的最大价值作为这次的最大价值
*/
if(j<Items_Weight[i]) {
dp[i][j] = dp[i-1][j];
}
/* 如果背包容量足够放下这件物品，那么就
* 比较不放入物品时的最大价值与放入此物
* 品时的最大价值谁大，将大的作为这次的最大价值
*/
else {
// GetMax(不放入物品的价值,此物品的价值+剩余空间的最大价值)
dp[i][j] = GetMax(dp[i-1][j],(dp[i-1][j-Items_Weight[i]]+values[i]));
}
System.out.print(dp[i][j]+" ");
}
System.out.println("");
}
// 至此求得解
return dp[Total_Item][package_weight_max];
}
/**
* 求最大值
* @param i
* @param j
* @return
*/
private static int GetMax(int i, int j) {
// TODO Auto-generated method stub
if(i>j) {
return i;
}else {
return j;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("计算矩阵如下: ");
int result = DPMethod();
System.out.println(String.format("12kg背包最多能装进价值为 %d 的物品", result));
}
}
OK，先记录到这！