关键词：
一、什么是01背包
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
二、01背包公式
01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。Pi表示第i件物品的价值。决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？我们只需要初始化第一行和第一列的数据，就可以根据状态转换方程进行计算所有的结果！我们只需要初始化第一行和第一列的数据，就可以根据状态转换方程进行计算所有的结果！我们只需要初始化第一行和第一列的数据，就可以根据状态转换方程进行计算所有的结果！
三、图解01背包
有了这张图和上面总结的公式，我们就可以很清晰的理解01背包算法了（倒序）！！！！！！！
- e2单元格：当只有一件物品e，包的容量是2时，装不进去，所以最大值为0
- a8单元格：物品包括a、b、c、d、e，容量为8时，F[i-1,j]=F[b,8]=9，F[i-1,j-Wi]+Pi=F[b,6]+6=9+6=15，两种情况取最大值，因此这里的最大值是15
四、java代码实现01背包（正序计算！！！！！！！）
先看结果图：
代码部分：
1 package com.niu.test; 2 3 /** 4 * Created by Administrator on 2017/10/3. 5 */ 6 public class ZeroOnePag { 7 8 /** 9 * w:代表物品的重量 10 * p:代表物品的价值 11 * pag:代表背包的大小 12 * @param args 13 */ 14 public static void main(String[] args) { 15 int[] w={3,5,2,6,4}; 16 int[] p={4,4,3,5,3}; 17 int pag=12; 18 table(pag,w,p); 19 20 } 21 22 static void table(int pag,int[] w,int[] p){ 23 int n=w.length; 24 //初始化f[0][1~pag]=0;f[1-n][o]=0;这样才能根据初始化根据公式推算其他的值！ 25 int[][] f=new int[n+1][pag+1]; 26 //01背包算法f[i][j]=MAX{f[i-1][j-w[i]]+p[i](j>=w[i],f[i-1][j])} 27 //算法核心部分：根据公式进行推算！！！！！ 28 for(int i=1;i<=n;i++){ 29 for(int j=1;j<=pag;j++){ 30 if(j>=w[i-1]){ 31 f[i][j]=Math.max(f[i-1][j-w[i-1]]+p[i-1],f[i-1][j]); 32 }else{ 33 f[i][j]=f[i-1][j]; 34 } 35 } 36 } 37 //输出表 38 for(int i=0;i<=n;i++){ 39 for(int j=0;j<=pag;j++){ 40 System.out.print(f[i][j]+"\t"); 41 } 42 System.out.print("\n"); 43 } 44 //输出最大值 45 System.out.println("能装的最大价值为："+f[n][pag]); 46 //输出装的物品 47 System.out.print("装的物品编号为："); 48 int x=pag; 49 for(int i=n;i>0;i--){ 50 if(f[i][x]>f[i-1][x]){ 51 System.out.print(i+"\t"); 52 x-=w[i-1]; 53 } 54 } 55 } 56 }
java入门到精通(03)
packageink.sdd.Java01;importorg.junit.Test;publicclassTest0001{//声明变量@Testpublicvoidtest01(){intage;//声明int型变量charchar1=‘r‘;//声明char型变量并赋值//变量名的明明规则：//1.变量名必须是一个有效的标识符//2.变量名不能重复//3.应该选择有意... 查看详情
java从入门到精通api01(代码片段)
文章目录1API11.1Object1.1.1概念1.1.2常用方法1.1.3toString()1.1.4equals(Objectobj)1.1.5hashCode()1.2String1.2.1特点1.2.2创建String对象1.2.3字符串连接效率1.2.4常用方法1.2.5测试1.3StringBuilder/StringBuffer1.3.1特点1.3.2练习：测试字符 查看详情
java之springaop入门到精通idea版（一篇文章精通系列）(代码片段)
...文章精通系列）一、设计模式-代理模式二、AOP思想及实现原理1、AOP思想2、实现原理（1）基于接口的动态代理：3、Spring中AOP的术语三、Spring注解驱动AOP开发入门1、写在最前2、注解驱动入门案例介绍3、案例实现4... 查看详情
jvm从入门到精通01(代码片段)
本笔记来源于学习尚硅谷的JVM课程前言1.为什么要学习JVM面试的需要（BATJ、TMD、PKQ等面试都爱问）中高级程序员必备技能：项目管理、调优的需要追求极客的精神：比如：垃圾回收算法，JIT，底层原理2... 查看详情
java入门到精通-第36讲-事件监听-坦克大战4
...件；事件监听者；事件处理方法； 任何一个类，只要实现了相应的接口，就可以去监听某个事件源；一个类要实现监听的基本步骤： a.实现相应的接口[KeyListener，MouseListener，ActionListener，WindowListener]b.把接口的处理方法... 查看详情
java入门到精通-第76讲-满汉楼系统3-实现闪屏登录
新开一个工作区：（文档、设计图、源代码）素材：图片、声音图片；MyEclipse切换到新的工作空间：Model2开发：com.mhl.view 界面 com.mhl.model 数据模型com.mhl.db 数据库UseCase用例图：用户... 查看详情
java入门到精通-第48讲-坦克大战12
...游戏界面？响应“开始新游戏”这个按钮就OK了；让JFrame实现一个接口：对用户不同的点击作出不同的处理//先删除旧的开始面板this.remove(msp);//显示，刷新JFrame----------- 查看详情
tkinterdesigner从入门到精通视频教程
...！欢迎使用TKinterDesigner！以下是《TKinterDesigner从入门到精通》哔哩哔哩视频教程第一讲：《TKinterDesigner从入门到精通》第一讲第二讲：《TKinterDesigner从入门到精通》第二讲第三讲：《TKinterDesigner从入门到精通... 查看详情
tkinterdesigner从入门到精通视频教程
...！欢迎使用TKinterDesigner！以下是《TKinterDesigner从入门到精通》哔哩哔哩视频教程第一讲：《TKinterDesigner从入门到精通》第一讲第二讲：《TKinterDesigner从入门到精通》第二讲第三讲：《TKinterDesigner从入门到精通... 查看详情
java入门算法（动态规划篇2：01背包精讲）(代码片段)
本专栏已参加蓄力计划，感谢读者支持❤往期文章一.Java入门算法（贪心篇）丨蓄力计划二.Java入门算法（暴力篇）丨蓄力计划三.Java入门算法（排序篇）丨蓄力计划四.Java入门算法（递归篇）丨... 查看详情
java入门到精通(07)
...性和行为封装起来，其载体就是类，类统称对客户隐藏其实现细节，这就是封装的思想65.类与类之间同样具有关系，类之间的关系被称为关联7两个类之间的关系有很多中 查看详情
清华大学出版社《c语言从入门到精通实例版》和《c语言从入门到精通》内容上有啥区别?
...】主要讲解哥德巴赫猜想、猴子选大王游戏、迷宫求解、背包问题求解、火车车厢重排、哈夫曼编码的实现、8皇后问题的实现、商人过河游戏、K阶斐波那契序列的实现、最短路径的实现等经典数据结构问题的解决；第4篇【项目... 查看详情
javascript实现动态规划(dynamicprogramming)01背包问题(代码片段)
...个分支，是求解决策过程最优化的过程。问题描述01背包问题是一个经典的算法问题，简单来说就是一个包要装许多水果，水果有体积和大小两个属性，怎么把包装满价值最大（最值钱）。专业描述问题... 查看详情
2021最新java学科全阶段视频教程（从入门到精通）
...学习路线包含了千锋教育Java学科全阶段视频教程（从入门到精通），涵盖了你所需要掌握的所有java前沿技术及知识点！2021年度全网最新，史上最全Java学习路线，从基础到项目实战应有尽有，牛批卡拉... 查看详情
git从入门到精通01
一、git到底是什么，有什么作用？ 1.根据百度百科的解释，Git(读音为/g?t/)是一个开源的分布式版本控制系统，可以有效、高速的处理从很小到非常大的项目版本管理。说白了就是一个免费软件，当多人开发一个项目时公共资... 查看详情
wpfmvvm从入门到精通7：关闭窗口和打开新窗口
... WPFMVVM从入门到精通1：MVVM模式简介WPFMVVM从入门到精通2：实现一个登录窗口WPFMVVM从入门到精通3：数据绑定WPFMVVM从入门到精通4：命令和事件WPFMVVM从入门到精通5：PasswordBox的绑定WPFMVVM从入门到精通6：RadioButton等一对多控件的绑定... 查看详情
java入门到精通-第84讲-网络基础
...项目；后台“启动服务器”服务器架设在公网上，是可以实现网络聊天的；----------------------普通版：服务器上有真正的IP地址；通过路由器进行数据转发；TCP/IP协议；传输控制协议和IP协议；Internet协议（TCP/IP）中国互联网1994年... 查看详情
java入门到精通-第39讲-线程.坦克大战7
如果没有做要求，用实现接口的方法写进程； 至少有继承的机会； 实际上，更多的情况下是多线程计算； 两个线程，t1/t2，同时启动； 创建了一只猪，创建了一只鸟； 第一个线程承载猪，第二... 查看详情