【程序员必会十大算法】之动态规划算法（背包问题）
相关标签： # java# java# 数据
1.动态规划算法
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)
2.背包问题（01背包）
有一个背包，容量为4磅，现有如下物品
①要求达到的目标为装入的背包的总价值最大，并且重量不超出
②要求装入的物品不能重复
①只有二维数组的版本
public class Main {
public static void main(String[] args) {
//注意 下面的w和value要一一对应，比如0号商品重量为1，价值为1500
int[] w = {1,4,3};//物品的重量
int[] value = {1500,3000,2000};//物品的价值
//这个j 可以自己进行变化
int capacity = 4;//背包的容量
//行 ： 就是几种物品
//列 ： 就是背包的容量从0开始 比如上面是4 那么列分别是 0 1 2 3 4
//+ 1 是因为还有第0行第0列
//行是0 表示没有商品，就算背包容量再大，价值也都是0
//列是0 表示背包没有容量，就算商品价值再高，价值也都是0
int[][] v = new int[w.length + 1][capacity + 1];
//首先将第0行第0列的所有值赋为0 原因在上面已经解释了
for (int i = 0;i < v.length;i++){
v[i][0] = 0;
}
for (int i = 0;i < v[0].length;i++){
v[0][i] = 0;
}
//然后进行二维数组的真正赋值
for (int i = 1;i < v.length;i++){//这是指从第1行开始，因为第0行已经赋值了，应该跳过
for (int j = 1;j < v[0].length;j++){//这是指从每一行的第1列开始，因为第0列已经赋值了，应该跳过
//如果装的东西的重量即w[i - 1]大于背包此时的容量即j，则直接将同一列的上一行的数据填入
if (w[i - 1] > j){
v[i][j] = v[i - 1][j];
}else {
//如果装的东西的重量即w[i - 1]小于等于背包此时的容量即j，则需要一次比较
//比较的内容是 不装这个东西，即上一次的价值v[i - 1][j]
//与 装这个东西之后，剩下的空间 再装 上一行之前的东西 的最大价值，即value[i - 1] + v[i - 1][j - w[i - 1]]的大小
v[i][j] = Math.max(v[i - 1][j],value[i - 1] + v[i - 1][j - w[i - 1]]);
}
}
}
//打印二维数组
for (int i = 0;i < v.length;i++){
for (int j = 0;j < v[0].length;j++){
System.out.print(v[i][j] + " ");
}
System.out.println();
}
}
}
结果
0 0 0 0 0
0 1500 1500 1500 1500
0 1500 1500 1500 3000
0 1500 1500 2000 3500
但是这个结果不知道3500是哪两个商品加上去的，所以需要改装一下。
②可以打印出哪两个商品的版本
public class Main {
public static void main(String[] args) {
//注意 下面的w和value要一一对应，比如0号商品重量为1，价值为1500
int[] w = {1,4,3};//物品的重量
int[] value = {1500,3000,2000};//物品的价值
//这个j 可以自己进行变化
int capacity = 4;//背包的容量
//行 ： 就是几种物品
//列 ： 就是背包的容量从0开始 比如上面是4 那么列分别是 0 1 2 3 4
//+ 1 是因为还有第0行第0列
//行是0 表示没有商品，就算背包容量再大，价值也都是0
//列是0 表示背包没有容量，就算商品价值再高，价值也都是0
int[][] v = new int[w.length + 1][capacity + 1];
//这个记录过程，当有物品加入的时候，就将相应值赋为1
int[][] path = new int[w.length + 1][capacity + 1];
//首先将第0行第0列的所有值赋为0 原因在上面已经解释了
for (int i = 0;i < v.length;i++){
v[i][0] = 0;
}
for (int i = 0;i < v[0].length;i++){
v[0][i] = 0;
}
//然后进行二维数组的真正赋值
for (int i = 1;i < v.length;i++){//这是指从第1行开始，因为第0行已经赋值了，应该跳过
for (int j = 1;j < v[0].length;j++){//这是指从每一行的第1列开始，因为第0列已经赋值了，应该跳过
//如果装的东西的重量即w[i - 1]大于背包此时的容量即j，则直接将同一列的上一行的数据填入
if (w[i - 1] > j){
v[i][j] = v[i - 1][j];
}else {
//如果装的东西的重量即w[i - 1]小于等于背包此时的容量即j，则需要一次比较
//比较的内容是 不装这个东西，即上一次的价值v[i - 1][j]
//与 装这个东西之后，剩下的空间 再装 上一行之前的东西 的最大价值，即value[i - 1] + v[i - 1][j - w[i - 1]]的大小
//v[i][j] = Math.max(v[i - 1][j],value[i - 1] + v[i - 1][j - w[i - 1]]);
if (v[i - 1][j] < value[i - 1] + v[i - 1][j - w[i - 1]]){
//这个时候说明有新物品加入
v[i][j] = value[i - 1] + v[i - 1][j - w[i - 1]];
path[i][j] = 1;//表示此时下标为 i-1 的物品 加入了
}else {
//这个时候说明没有新物品加入
v[i][j] = v[i - 1][j];
}
}
}
}
//打印二维数组
System.out.println("打印二维数组=====");
for (int i = 0;i < v.length;i++){
for (int j = 0;j < v[0].length;j++){
System.out.print(v[i][j] + " ");
}
System.out.println();
}
//打印加入过程
System.out.println("打印加入数组=====");
for (int i = 0;i < path.length;i++){
for (int j = 0;j < path[0].length;j++){
System.out.print(path[i][j] + " ");
}
System.out.println();
}
// for (int i = 0;i < path.length;i++){
// for (int j = 0;j < path[0].length;j++){
// if (path[i][j] == 1){
// System.out.println("下标为" + (i - 1) + "的物品加入了");
// }
// }
// }
System.out.println("打印加入过程=====");
//j是动态变换的，这次path等于1的时候，要跟 去掉此次加入的物品的容量 的上一次path为1的时候作比较
int i = path.length - 1;//从最大下标开始遍历
int j = path[0].length - 1;
while (i > 0 && j > 0){
if (path[i][j] == 1){
//说明此时加过东西
System.out.println("下标为" + (i - 1) + "的物品加入了");
//然后减去此东西的重量
j = j - w[i - 1];
}
//因为此行已经统计过了 所以从上一行继续开始找，有没有装过东西的时候，如果有的话，其重量加上刚刚减去的重量是不是等于最开始的j
i--;
}
}
}
结果
打印二维数组=====
0 0 0 0 0
0 1500 1500 1500 1500
0 1500 1500 1500 3000
0 1500 1500 2000 3500
打印加入数组=====
0 0 0 0 0
0 1 1 1 1
0 0 0 0 1
0 0 0 1 1
打印加入过程=====
下标为2的物品加入了
下标为0的物品加入了
文章来源： https://blog.51cto.com/u_15824619/5746637
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
