温故01背包问题

硅谷探秘者 5648 0 0

01背包问题是动态规划算法的一个经典例题:

题目:


	  在n种物品中选取若干件(每种物品只有一件只能选择一次)
	  放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3],wigth[n],
	  与之相对应的价值为value[1],value[2]value[3],value[n].
	  求解怎么装物品可使背包里物品总价值最大
	
package day11;
public class O1背包 {
	/*
	 * 在n种物品中选取若干件(每种物品只有一件只能选择一次)
	 * 放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3],wigth[n],
	 * 与之相对应的价值为value[1],value[2]value[3],value[n].
	 * 求解怎么装物品可使背包里物品总价值最大
	 */
	static int wigth[]= {0,4,3,2,1,5};//物品质量
	static int value[]= {0,1,3,6,3,1};//物品价值
	static final int NUM=5;//物品个数
	static final int W=10;//背包容量
	static int dept[][]=new int[NUM+1][W+1];
	    //标记数组(表示第 i 个物品在装入背包容量为 j 的背包时的最大价值)
	public static void main(String[] args) {//主函数
		for(int i=1;i<=NUM;i++) {//表示第i个物品
			for(int j=1;j<=W;j++) {//表示当前背包容量
				if(wigth[i]<=j) {//可以装
					dept[i][j]=max(dept[i-1][j],dept[i-1][j-wigth[i]]+value[i]);
					    //装还是不装?
				}else {//不可以装
					dept[i][j]=dept[i-1][j];//肯定不装
				}
				System.out.print(dept[i][j]+"\t");
				    //输出前i个物品 在装入背包容量为 j 的背包时 的最大价值
			}
			System.out.println();
		}
		System.out.println("最大价值:"+dept[NUM][W]);
	}
	public static int max(int x,int y) {//比较装入好,还是不装入好
		return x>y?x:y;
	}
}

这个问题的主要难点就在于理解一句话:

static int dept[][]=new int[NUM+1][W+1];//标记数组(表示第 i 个物品在装入背包容量为 j 的背包时的最大价值)

如果理解了这个二维数组,那么剩下的代码就好理解了。

猜你喜欢
框架 7383 多么痛的领悟~分离资源打后运行项目,启动失败数据源初始化失败~检查,这种情况下没有打印错误日志,首先配置一下日志,将错误报告在控制台中打印出来。resources文件夹下创建一个
数据结构与算法 6811 八皇后,是一个古老而著名的,是回溯算法的典型案例。该是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行
数据结构与算法 3379 迷宫!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
数据结构与算法 4327 。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。packageproblem;/***汉诺塔*@authorLENOVO**/publicclassHanoi{publicv
数据结构与算法 11959 描述给定一个int类型一维数组a[],和一个int类型的数值b。编写一个程序,判断数组中有没有两个数(a[i],a[j])的和等于b,如果存在,返回两个数在a数组中的下表
数据结构与算法 6249 描述:渗透,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然后继续渗透,判断此图中的白纸最终是否能够全部被墨水染上色,若能需要输出所有白纸
数据结构与算法 8027 1.描述::上面有一个迷宫,灰色部分代表不能通过,白色部分代表可以通过,现在从a点出发,能否找到一条路径到达b点,如果能,输出此路径。下面采用试探法求解,采用栈结构保存每一步的内容(括坐标
java基础 6785 多线程带来的:线程有时候回和其他线程共享一些资源,比如内存、数据库等。当多个线程同时读写同一份共享资源的时候,可能会发生冲突。这时候,我们就需要引入线程“同步”机制,即各位线程之间要有顺序使用
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2 2022年10月  2 2022年12月  5 2023年01月  3
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。