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