0-1背包java动态规划)
第2章 动态规划
2.1 动态规划基本介绍
1)动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法
2)动态规划算法与分治算法类似,其基本思想也还是将待求解问题分解成若干个小问题,先求解子问题,然后从这些子问题的解得到原问题的解
3)与分治算法不同的是:以用于用动态规划求解的问题,经分解得到子问题往往不是相互独立的(即:下一个子阶段的求解是建立在上一个子阶段的基础上。进行进一步的求解)
4)动态规划是可以通过填表的方式逐步推导,得到最优解
2.2 0-1背包问题
3)思路分析和图解
- 背包问题主要是指一个给定容量的背包,若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分为0-1背包和完全背包(完全背包指的是:每种物品都有无限件可用)
- 这里的问题属于0-1背包,即每个物品最多放一个,而无限背包可以转换成0-1背包
思路分析:
算法的主要思想:利用动态规划来解决,每次遍历到第i个物品,根据w[i] 和v[i] 来确定是否需要将该物品放入到背包中,即对于给定的n个物品,设v[i] 、w[i]分别为第i个物品的价值和重量,C为背包的容量,再令v[i] [j] 表示在前i个物品中能够装入容量为j的背包中的最大价值。则有如下结果
-
v[i] [0] = v[0] [j] = 0;
-
规定不能装任何东西的时候,或者背包的容量为0的时候,最大价值就是0
-
当w[i] > j ; v[i] [j] = v[i-1] [j];
- //当准备加入新增的物品的容量大于当前背包的容量时,此时背包的最大价值就是加入该物品之前,其他已经放入到背包中的最大价值
-
当j > =w[i] ; v[i] [j] = max{v[i-1] [j], v[i] v[i-1] [ j -w[i] ] v[i] }
- //当准备加入的新增物品的容量小于等于当前背包的容量
- 3.如果准备加入的物品的重量比背包包容量小的话,有两种选择 1、把当前物品放入背包 2、不把当前物品放入背包,这两种选择取决于 放入当前物品后是否会导致背包容量溢出,**如果溢出的话,就比较当前背包的价值与溢出的物品的 价值大小,**如果溢出前物品的价值大,就不放入当前物品。 如果溢出前的物品价值小,就放入当前物品,把之前放入的物品取出。 如果不溢出的话,把当前物品也加入到背包中,之前的物品也不需要取出。
-
//装入的方式:
j :背包的容量
w[i] : 第i物品的重量
v[i] : 第i物品的价值
v[i-1] [j] :第i个物品之前的装入最大价值
v[i-1] [j - w[i]] : 装入i-1个物品,到剩余空间的最大值
代码实现
package com.ldm.dynamic;
import java.util.Arrays;
/**
* @author 梁东明
* 2022/9/11
* 人生建议:看不懂的方法或者类记得CTRL 点击 看看源码或者注解
* 点击setting在Editor 的File and Code Templates 修改
*
* 0-1背包问题
*
*/
public class KnapSackProblem {
public static void main(String[] args) {
int[] w = {1,4,3}; //物品的重量
int[] val = {1500,3000,2000};//物品的价值
int m = 4; //背包的容量
int n = val.length; //物品的个数
//创建二维数组表示 前i个商品能够装入容量为j的背包的最大价值
int[][] v = new int[n 1][m 1];
//为了记录物品的放置情况,再定义一个二维数组
int[][] path = new int[n 1][m 1];
//规定不能装任何东西的时候,或者背包的容量为0的时候,最大价值就是0
for (int i = 0; i < v.length; i ) {
v[i][0] = 0; //第一列设置为0(背包的容量为0的时候)
}
/*
for (int i = 0; i < v[0].length; i ) {
v[0][i] = 0; //第一行设置为0(背包不装任何东西的时候)
}
*/
//上面三行代码可以用这一行代码代替(CTRL 点击 看看源码,这样你就懂了)
//很多方法,都不需要我们重复造轮子,JDK自己就已经封装好了,我们直接调用就行了
Arrays.fill(v[0], 0);//第一行设置为0(背包不装任何东西的时候)
//动态规划
for (int i = 1; i < v.length; i ) { //不处理第一行,因为上两步已经把它们置为0了
for (int j = 1; j < v[i].length; j ) { //不出来第一列,
//当准备加入新增的物品的容量大于当前背包的容量时,
//此时背包的最大价值就是加入该物品之前,其他已经放入到背包中的最大价值
if ( w[i-1] > j){ //本来应该是w[i] > j 的,但是我们的程序是从1开始的,所以要减1
v[i][j] = v[i-1][j];
}
//3.如果准备加入的物品的重量比背包包容量小的话,
// 有两种选择 1、把当前物品放入背包 2、不把当前物品放入背包,
// 这两种选择取决于 放入当前物品后是否会导致背包容量溢出,
// 如果溢出的话,就比较当前背包的价值与溢出的物品的价值大小
// 如果溢出前物品的价值大,就不放入当前物品。
// 如果溢出前的物品价值小,就放入当前物品,把之前放入的物品取出。
// 如果不溢出的话,把当前物品也加入到背包中,之前的物品也不需要取出。
else if (j >= w[i-1]){//本来应该是j >= w[i] 的,但是我们的程序是从1开始的,所以要减1
// v[i][j] = Math.max(v[i-1][j],val[i-1] v[i-1][j-w[i-1]]);
if (v[i-1][j] > val[i-1] v[i-1][j-w[i-1]] ){
v[i][j] = v[i-1][j];
}else {
v[i][j] = val[i-1] v[i-1][j-w[i-1]];
path[i][j] = 1;
}
}
}
}
//遍历二维数组,输出元素
System.out.println("背包中物品的价值变化");
for (int i = 0; i < v.length; i ) {
for (int j = 0; j < v[i].length; j ) {
System.out.print(v[i][j] "\t");
}
System.out.println();
}
System.out.println("================");
int i = path.length - 1; //行的最大下标
int j = path[0].length - 1; //列的最大下标
//从path的最后面开始找,看看到底背包中最后放置了哪几个物品
while ( i > 0 && j > 0){
if (path[i][j] == 1){
System.out.println("第 " i " 个物品放入到背包中");
j -= w[i-1];
}
i--;
}
System.out.println("背包中物品的最大价值是:" v[n][m]);
}
}
本次0-1背包算法 的教程出自韩顺平的数据结构与算法
数据结构和算法教程,哔哩哔哩详细教程
在 156 - 159p.
最后,认识一下,我是小白。努力成为一名合格的程序员。期待与你的下次相遇。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbehe
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01