共计 4316 个字符，预计需要花费 11 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、动静布局算法的概述
2、背包问题
3、动静布局算法解决背包问题
3、1 不可反复装入商品
3、2 思路剖析
1、动静布局算法的概述
（1）动静布局算法的思维是：将大问题分为小问题进行解决，使得一步步取得最优解的解决算法。
（2）动静标准算法与分治算法很相似，思维都是以待解决问题先分解成 n 个子问题，先求解子问题，而后从子问题中失去原问题的解。
（3）动静布局求解的问题与分治算法不同的点在于，通过合成进去的子问题不是互相独立的，下一个子问题的求解是建设在上一个子问题解决的求解根底上的，顺次递进获取最终解。
（4）动静布局能够通过填表的形式一步步推动，最终失去最优解。
2、背包问题
这里就有一个背包问题了，有一个容量为 4 磅的背包，须要装入如下表 1 的物品，怎样才能使装入包中的商品最值钱且不超过 4 磅重？
图片
3、动静布局算法解决背包问题
下面的背包问题，放入商品的总品质不能超过 4 磅且要实现背包装入商品价值的最大化，这里假如放入的商品是不能反复的，可用一个二维表格来示意。
3、1 不可反复装入商品
我先画一个表格 2，而后会对这个表格 2 进行具体的阐明，如下所示；
图片
阐明：列示意背包能装多大的分量，横示意物品的类型和商品数量，行和列穿插而呈现的数据表示背包能装的物品总和的最大价值。
好，咱们当初对表 2 的数据分析一下，第一行的数据全副为 0，这个能够了解吧？不论背包能放多大的分量，只有不放入物品，那就是 0 咯；第一列的数据全副为 0，是因为背包能装 0 磅；咱们看第二行第二列的数据到第二行第五列的数据，首先第二行能放的物品只能是鞋子且不能反复对不对？那不论背包（装的分量大于等于 1 磅）能装多少磅的物品，都是只能放 1 磅的鞋子对不对？那天然就是 1500 了。
咱们看第三行第二列到第三行第五列的数据，第三行能放入的物品是鞋子、音响且同一个物品不能放超过 1 个，第三行的第二列到第三行的第四列只能放 1 磅的鞋子，放不下音响（音响 4 磅重），所以就是 1500 了，而第三行的第五列刚好能放 4 磅的音响，而且放一个音响比放一双鞋子更值钱对不对？
第四行能够放的商品有鞋子、音响和电脑，好，当初看第四行的第二列到第四行的第三列，因为第二列和第三列是只能装 1 磅和 2 磅对不对？那就只能放一双鞋子了，所以就是 1500 了；第四行的第四列能装 3 磅，那就是能够放一双鞋子或者一台电脑，因为电脑比鞋子更值钱对不对，所以放电脑更好点，所以就是 2000 了；看第四行的第五列，背包能够装 4 磅，那这外面就有较好一点的两种计划抉择了，一种是放一双鞋子和一台电脑，另一种是只放一台音响，一看放一双鞋子和一台电脑的计划更值钱对不对，所以是 1500+2000 就是 3500 了。
从表 2 能够小结一下
（1）横行示意背包容量从 0 到指定容量的各种状况，这是第一步的分，将大容量的背包先转化为小容量背包，算出子问题的最优解，而后一步步加大容量，算出最终问题的最优解。
（2）纵行示意商品信息，且第一横行为空值，作为初始数据的对比值；纵行是第二步的分，先将一个商品放入背包中，算出最优解，逐步减少商品类型和商品数量，算出最终最优解。
（3）最终表格的最右下角的格子，即为数据的最优解；看表 2 最右下角的数据 3500，是不是最优解。
3、2 思路剖析
（1）利用动静布局来解决，假如给定的 n 个物品，设 v[i]、w[i] 分 别为第 i 个商品的价值和分量，C 为背包的容量。
（2）每次遍历到的第 i 个商品，依据 w[i] 和 v[i] 来确定是否须要将该商品放入背包中；这句话说的是什么意思呢？我举个例子，你们就了解了，看表 2 的第四行的第四列的 2000 这个数据，首先第四列背包最大容量是 3 磅对不对？第四行能放的商品有鞋子、音响和电脑对不对？然而音响比背包的容量更大，所以就只能放鞋子和电脑，鞋子和电话的分量和超过 3 磅对不对，所以又只能从鞋子和电脑外面筛选一个放进去，因为电脑比鞋子更值钱对不对？所以放电脑价值更大对不对？所以是依据 w[i] 和 v[i] 来确定是否须要将该商品放入背包中。
（3）再令 vi 示意在前 i 个商品中可能装入容量为 j 的背包中的最大价值；这句话又是什么意思啊？我再举个例子，看表 2 的第三行第五列的 3000，这时候 i 就是 2，j 就是 4，vi 就是 v2，也就是 v2 为 3000；第二行只能装的商品是鞋子对不对？第三行能装入的商品蕴含第二行装入的商品，也就是说第三行能抉择装入的商品是鞋子和音响；如果鞋子和音响同时放入背包（背包容量为 4 磅，j=4）必定是装不下的对不对？所以从鞋子和音响外面选最值钱的放入背包中，所以就是 vi 示意在前 i 个商品中可能装入容量为 j 的背包中的最大价值。
当初咱们从思路剖析和表 2 中可能总结出以下几条公式；
（1）vi = v0 = 0，其中 i 示意第几行，j 示意第几列；看表 2，第一列的数据是不是 0？第一行的数据是不是也是 0？
（2）当 w[i] > j 时，有 vi = vi-1，w 示意第 i+1 行商品的分量；举例：看表 2 中的第三行的第二列，i = 2，w[i] = 4，j = 1，v2 = v2-1 = 1500。
（3）当 j >= w[i] 时，有 vi=max{vi-1,vi-1]+v[i]}，v[i] 示意第 i+1 行商品的价格；举例：看表 2，看第四行的第五列数据，j = 4，i = 3，w[3] = 3，v[3] = 2000，那么 v3 = max{v3-1 , v3-1]+v[3]} = max{3000 , 3500}，所以 v3 = 3500。
好，咱们当初用代码实现一把；
（1）新建一个 Test 类：
package com.xiaoer.demo;
/**
- 动静布局: 背包问题
**/
public class Test {
public static void main(String[] args) {Test test = new Test();
// 商品名字数组
String[] nameArr = {"鞋子", "音响", "电脑"};
// 商品分量数组
int[] weightArr = {1/* 鞋子 */, 4/* 音响 */, 3/* 电脑 */};
// 商品价格数组
int[] priceArr = {1500/* 鞋子 */, 3000/* 音响 */, 2000/* 电脑 */};
// 背包容量
int packageCapacity = 4;
// 把不可反复的商品装入背包
test.backpackWithoutRepeat(nameArr, weightArr, priceArr, packageCapacity);
}
/**
* 装入背包
* @param nameArr 商品名字数组
* @param w 商品分量数组
* @param priceArr 商品价格数组
* @param packageCapacity 背包容量
*/
private void backpackWithoutRepeat(String[] nameArr, int[] w, int[] priceArr, int packageCapacity) {
/**
* 申明一个能装入 0、1、2、3 磅...... 的背包的二维价格表；举例：就好比 v 数组是表 2 的数据
*/
int[][] v = new int[nameArr.length + 1][packageCapacity + 1];
// 构建可能装入背包的二维数组
// 值为 0 时阐明不会装进背包, 值为 1 阐明可能装入背包
int[][] contentArr = new int[nameArr.length + 1][packageCapacity + 1];
/**
* 为什么 i 一开始是 1 不是 0？看表 2 的数据，是不是第一行全是 0 啊
*/
for (int i = 1; i < v.length; i++) {
/**
* 为什么 j 一开始是 1 不是 0？看表 2 的数据，是不是第一列全是 0 啊
*/
for (int j = 1; j < v[i].length; j++) {
/**
* 文章中当 w[i] > j 时，就有 v[i][j] = v[i-1][j]；* 因为咱们程序 i 是从 1 开始的，因而原来公式中的 w[i] 批改成 w[i-1]；* 以后商品 > 背包容量, 取同列上一行数据
*/
if (w[i - 1] > j) {v[i][j] = v[i - 1][j];
} else {
/**
* 以后商品 <= 背包容量, 对两局部内容进行比拟;
* 第一局部, 该列上一行数据
*/
int onePart = v[i - 1][j];
/**
* 还记得文章中写的 当 j >= w[i] 时，有 v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 这个公式成立吗？* priceArr[i - 1]: 以后商品价格;
* w[i - 1]: 以后商品分量;
* j - w[i - 1]: 去掉以后商品, 背包残余容量;
* 不可反复: v[i - 1][j - w[i - 1]]: 在上一行, 取残余分量下的价格最优解;
*/
int otherPart = priceArr[i - 1] + v[i - 1][j - w[i - 1]];
/**
* 取最大值为以后地位的最优解
*/
v[i][j] = Math.max(onePart, otherPart);
/**
* 如果最优解蕴含以后商品, 则示意以后商品曾经被应用, 进行记录
*/
if (otherPart == v[i][j]) {contentArr[i][j] = 1;
}
}
}
}
// 不能反复的场景中
// 如果该地位的标记位为 1, 阐明该商品参加了最终的背包增加
// 如果该地位的标记位为 0, 即便该地位的价格为最大价格, 也是从其余地位援用的价格
// 因为不能反复, 所以每行只取一个数据参加最终计算, 并只判断在最大地位该商品是否参加
// 该最大地位会随着曾经遍历出其余元素而对应一直减小, 直到为 0
// 二维数组最初一个元素必然是最大值, 然而须要晓得该最大值是本身计算的 还是比拟后援用其余的
int totalPrice = 0;
// 最大行下标数, 即商品数
int maxLine = contentArr.length - 1;
// 最大列下标数, 即分量
int maxColumn = contentArr[0].length - 1;
for (;maxLine > 0 && maxColumn > 0;) {
// 等于 1 示意在该地位该商品参加了计算
if (contentArr[maxLine][maxColumn] == 1) {
// 遍历后, 对分量缩小, 下一次从残余分量中取参加商品
maxColumn -= w[maxLine - 1];
totalPrice += priceArr[maxLine - 1];
System.out.println(nameArr[maxLine - 1] + "退出了背包");
}
// 因为不能反复
// 所以如果该商品参加了背包容量, 则必定残余的最大地位处参加,
// 否则跟该数据无关, 间接跳过
maxLine--;
}
System.out.println("背包可包容的最大价值:" + totalPrice);
}
}
程序运行后果如下所示；
图片
