关键词：
今天学习01背包。因为01背包在暑假学习过，所以上网看了一下文章，就能写出来了。主要还是一种动态规划的思想，设置背包的【容量】进行增长，【物品】进行增长。只要满足【当前物品】的【价值】=ｍａｘ｛
不放入【当前物品】的价值，
从【当前容量】中腾出【当前物品】的【重量】的物品。即丢弃掉掉一些东西，是【当前物品】能放入【当前容量】的背包中。
｝
表达能力有限，附上学习链接：动态规划之01背包问题（最易理解的讲解）
不过感觉这篇文章的求解矩阵画的有问题。
我的Ｊａｖａ代码：
1 import java.util.*; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 int []w={2,2,6,5,4}; 8 int []v={6,3,5,4,6}; 9 int weight=10; 10 _01package problem=new _01package(w,v,weight); 11 12 13 } 14 15 } 16 17 class _01package{ 18 //价值、重量 19 int [][] matrix; 20 List<Integer> solve=new ArrayList<Integer>(); 21 _01package(int [] w,int [] v,int weight){ 22 23 int i,j; 24 int len=w.length; 25 matrix=new int[len+1][weight+1];//构建求解数组 26 for(i=0;i<weight+1;i++) matrix[0][i]=0;//第一行为0 27 for(i=0;i<len+1;i++) matrix[i][0]=0;//第一列为0 28 //动态规划 29 for(i=1;i<len+1;i++){ //从上到下【不断将物品放入背包】【i】代表物品 30 for(j=1;j<weight+1;j++){ //从左到右【背包的容量不断扩充】【j】代表当前容量 31 if(j>w[i-1]){//【当前背包容量】比【将要放入的物品】的【重量】大 32 matrix[i][j]=Math.max 33 (matrix[i-1][j], //选择不放 34 matrix[i-1][j-w[i-1]]+v[i-1]); //让背包腾出w[i-1]，即【当前物品】的【重量】的空间，选择放入 35 }else{ //放不进。拷贝【上一个物品】的重量 36 matrix[i][j]=matrix[i-1][j]; 37 } 38 } 39 } 40 System.out.println("求解矩阵："); 41 System.out.print(this); 42 //回溯 43 j=weight;//最后一列 44 for(i=len;i>0;i--){//对行进行遍历 45 if(matrix[i][j]>matrix[i-1][j]){//增减物品时，价值增加了。说明放入了物品 46 j-=w[i-1]; 47 solve.add(i); 48 } 49 } 50 System.out.print("应该放入背包的物品："); 51 for(i=0;i<solve.size();i++) System.out.print(solve.get(i)+" "); 52 System.out.println(); 53 } 54 55 public String toString(){ 56 int row = matrix.length;//行数 57 int col =matrix[0].length;//列数 58 String str=new String(""); 59 int i,j; 60 for(i=0;i<row;i++){ 61 for(j=0;j<col;j++){ 62 str+=Integer.toString(matrix[i][j]); 63 str+="\t"; 64 } 65 str+="\n\n"; 66 } 67 return str; 68 } 69 }
求解矩阵：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 6 6 6 6 6 0 0 0 6 6 9 9 9 9 9 9 0 0 0 6 6 9 9 9 9 11 11 0 0 0 6 6 9 9 9 10 11 13 0 0 0 6 6 9 9 12 12 15 15
运行结果：
acm：动态规划，01背包问题
题目：有n件物品和一个容量为C的背包。（每种物品均仅仅有一件）第i件物品的体积是v[i]，重量是w[i]。选一些物品装到这个背包中，使得背包内物品在整体积不超过C的前提下重量尽量大。解法：两种思路：第一种：d(i,j)表示“... 查看详情
动态规划入门讲稿
目录 第一讲01背包问题 第二讲完全背包问题 第三讲多重背包问题 第四讲混合三种背包问题 第五讲LIS问题 第一讲:01背包问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]... 查看详情
01背包(代码片段)
1初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初... 查看详情
例9.1101背包问题
【例9.11】01背包问题链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1267时间限制:1000ms 内存限制:65536KB【题目描述】一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,... 查看详情
acwing（基础）---01背包和完全背包多重背包问题(代码片段)
初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候... 查看详情
01背包
...有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问... 查看详情
fzu2214knapsackproblem（01背包）
...的价值为Vi，重量为Wi,把这些物品放入一个重量限制为B的背包中，使得背包内的物品在重量不超过B的前提下，价值尽量大，输出最大价值1<=n<=5001<=B,w[i]<=10000000001<=v[1]+v[2]+...+v[n]<=5000思路：我们从范围中可以看到这... 查看详情
01背包问题模板代码(代码片段)
01背包问题Pleiades_Antares打个模板，基本上01背包都这个样子了～从百度上摘来两张图，简单可以说明01背包了应该这是我找的第一张这是我找的第二张01背包是DP的内容，DP刚开始学一般都是记忆化搜索嘛，那就是优化过的搜索问... 查看详情
纯01背包问题-dp(代码片段)
纯01背包问题骨头收集者有一个大袋子，里面装有V，而且在收集骨头的过程中，很明显，不同的骨骼具有不同的值和不同的体积，现在给定沿途的每个骨骼的值，您能否计算出骨骼收集器可以获得的总值的... 查看详情
hdu5887herbsgathering（搜索求01背包）
http://acm.hdu.edu.cn/showproblem.php?pid=5887题意：容量很大的01背包。 思路：因为这道题目背包容量比较大，所以用dp是行不通的。所以得用搜索来做，但是需要一些剪枝，先按体积排序，优先考虑体积大的物品，这样剪枝会剪得多... 查看详情
poj-1948二维01背包
...方程很简单粗暴dp[i][j][k]:用前i物品使得容量分别为j和k的背包恰好装满背包的调用只需一次即可,第一次T就是每次check都丧心病狂地背包一次对于sum的枚举,其实ij枚举到sum/2就可以了#include<cstdio>#include<cstring>#include<iostre... 查看详情
01背包问题(代码片段)
01背包有n种物品，背包重量为V，接下来有每个背包的重量w[i],价值v[i],求最大的总价值。这是01背包的基本样式，首先分析问题，有两种状态，放还是不放，显然得出了我们第一个dp方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])表示前i... 查看详情
动态规划/背包问题背包问题第一阶段最终章：混合背包问题
前言今天是我们讲解动态规划专题中的「背包问题」的第十一篇。今天将会学习「混合背包」问题，同时也是我们「背包问题」的第一阶段的最后一节。今天首先会和大家回顾之前学过的三种背包问题。然后通过一道「混合背包... 查看详情
01背包完全背包多重背包分组背包总结
文章目录一、01背包问题二、完全背包问题三、多重背包问题四、分组背包一、01背包问题n个物品，每个物品的重量是，价值是，背包的容量是若每个物品最多只能装一个，且不能超过背包容... 查看详情
01背包问题-动态规划算法
...有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问... 查看详情
背包问题（01背包，完全背包，多重背包）
...http://www.cnblogs.com/daoluanxiaozi/archive/2012/05/06/2486105.html 背包问题，经典有背包九讲。01背包 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些... 查看详情
背包九讲(代码片段)
目录第一讲01背包第二讲完全背包第三讲多重背包第四讲混合背包第五讲二维费用的背包问题第六讲分组背包第七讲有依赖的背包问题第八讲背包问题求方案数第一讲01背包01背包是每种武平只能选择一次，计算出最大价值的问题... 查看详情
01背包模板全然背包and多重背包（模板）
...g.com/tanky-woo/archive/2010/07/31/121803.html模版就直接贴代码：01背包模板：/*01背包问题01背包问题的特点是，">每种物品仅有一件。能够选择放或不放。01背包问题描写叙述：有N件物品和一个容量为V的背包 查看详情