精华内容
下载资源
问答
  • 日常吐槽,日常打代码,理论可以去看其他博客,只贴出代码,代码有注释public ...//自底向上,若最后一个物体的重量小于背包的总容量,取最后一个物体的重量为界限//小于w[n]都放不不了for(int j=0;j<=jMax;j++...

    日常吐槽,日常打代码,理论可以去看其他博客,只贴出代码,代码有注释

    public static int Knapsack(int v[],int w[],int c,int n,int m[][])

    {

    int jMax=Min(w[n]-1,c);//自底向上,若最后一个物体的重量小于背包的总容量,取最后一个物体的重量为界限

    //小于w[n]都放不不了

    for(int j=0;j<=jMax;j++)m[n][j]=0;//背包容量小于最后一个物品的重量,不能放入该物品

    for(int j=w[n];j<=c;j++) m[n][j]=v[n];//大于w[n]能放入

    int i;

    for(i=n-1;i>0;i--){//从n-1到1

    jMax=Min(w[i]-1,c);

    for(int j=0;j<=jMax;j++){//背包容量j小于物体w[i],则不能放入

    m[i][j]=m[i+1][j];

    }

    for(int j=w[i];j<=c;j++) {

    m[i][j]=Max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//大于则尝试放入,与不放入相比,区总价值大的

    }

    }

    m[0][c]=m[1][c];//此时m[1][c],m[2][c],m[3][c]......m[n-1][c],m[n][c]的最优值已算出来

    if(c>=w[0]){

    m[0][c]=Max(m[i+1][c],m[i+1][c-w[1]]+v[0]);//此时i等于0

    }

    return m[0][c];

    }

    //输出选取物体的下标,从0开始

    public static void Tracback(int v[],int w[],int c,int n,int m[][]){

    int x[] = new int[5];

    for(int i=0;i

    if(m[i][c]==m[i+1][c]){//相等则该物体不屈

    x[i]=0;

    }else{

    c=c-w[i];//取该物体后背包容量建w[i]

    x[i]=1;

    }

    }

    if(m[n][c]>w[n]) {//只剩最后一个一物体,若背包容量能装下,则一定取

    x[n]=1;

    }else{

    x[n]=0;

    }

    for(int i=0;i

    System.out.println(x[i]);

    }

    }

    public staticint Max(int a,int b){

    if(a>=b){

    return a;

    }else{

    return b;

    }

    }

    public static int Min(int a,int b){

    if(a

    return a;

    }else{

    return b;

    }

    }

    代码测试

    //测试函数

    @org.junit.Test

    public void Test1(){

    //背包容量

    int c=10;

    //物体个数

    int n=4;

    //物品质量

    int w[]={2,2,6,5,4};

    //物品价值

    int v[]={6,3,5,4,6};

    int m[][] =new int[200][200];

    // int m[][] ={};

    System.out.println(ZeroOne.Knapsack(v,w,c,n,m));

    ZeroOne.Tracback(v,w,c,n,m);

    }

    展开全文
  • 01背包问题 动态规划 ** 1.动态规划 什么是动态规划动态规划就是将一个大问题不断向下拆分成小问题,直到拆分出的小问题可以求出其解,然后将小问题的解不断的向上合并,最终得到大问题的解决方案。   2.01背包...

    **

    01背包问题 动态规划

    **

    1.动态规划

    什么是动态规划?动态规划就是将一个大问题不断向下拆分成小问题,直到拆分出的小问题可以求出其解,然后将小问题的解不断的向上合并,最终得到大问题的解决方案。
      
    2.01背包问题

    一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大?
      
    3.简单思路

    1.01背包问题与背包问题的区别在于,01背包,物品的选择只有两种一种是拿,另一种是不拿,而背包问题在于,物品可以只取一部分。所以01背包问题不能用贪心算法解决。
    2.以dp[i][j]表示用i种物品,重量为j表示所取得的价值。
    3.对于第i种物品,如果第i种物品重量大于j,就证明第i种物品肯定不能取,这时的dp[i][j]=dp[i-1][j]
    4.如果第i种物品重量小于j,那就会出现两种情况,采用i的话,物品价值dp[i][j]=采用前面的i-1种物品,所占用的重量为j-i.getweight,所产生的价值+第i 种物品的价值。如果不采用i,价值为dp[i-1][j]。换成数学表达式就是dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);
    5.比如当i=5,j=10时,dp[5][10]就代表了所取得的最大价值。到这里我们就完成了任务的一半,接下为我们要寻找到底哪些物品放入了背包,从前面的表达式我们可以发现,当dp[i][j]=dp[i-1][j-weight]时,这时为i的物品就会放入背包,所以我们从结果,开始往回走,遇到这种情况,就说明有物品放入背包,然后物品数减1,重量减去为i的重量,继续,最后就能求出哪 些物品放入背包了。

    例题:

    1.题目描述:

    有如下5种物品,小明的书包最多只能装下8公斤的物品,小明特别贪心,思考怎么选择使自己书包能装下并且得到的价值最大。

    物品1:6公斤   价值48元
    物品2:1公斤    价值7元
    物品3:5公斤    价值40元
    物品4:2公斤    价值12元
    物品5:1公斤    价值8元

    2.解题思路:

    其实我们正常思维,一般会想,我要尽量装满8公斤,把最大的价值求出来,可是这样的话,就需要用到递归,递归能解出来,只是算法难度高。但是什么是动态规划,动态规划就是逆着来,我要求装8公斤的物品怎么装使得价值最大。我可以先考虑装0公斤,最大价值,再考虑装1公斤最大价值,考虑装2公斤最大价值,装3公斤最大价值,把前面都记录下来。用另外一个temp[i][j]数组记录下来。i呢表示我现在出现的物品的数量,当i循环到最后一个数量的时候就结束了嘛。自己想象一下,我虽然有5件物品,先只给你一件,你判断能不能装下,能装下,那么你就看你装下这件物品,和不装下这件物品哪个价值高,那么记录下来即可。具体填下下面的表试下,真正会填表就差不多了

          0  1  2  3  4  5   6    7    8
          0  0  0  0  0  0   0    0    0
    6 48  0  0  0  0  0  0   48  48   48
    1 7   0  7  7  7  7  7   48  55   55
    5 40  0  7  7  7  7  40  48  55   55
    2 12  0  7  12 19 19 40  48  55   60
    1 8   0  8  15 20 27 40  48  56   63 
    

    这个表是怎么来的呢?,举个例子,当我横着一排一排填,因为最开始只掉一件物品,开始掉重量是6的物品,到6的时候就能装下了,所以temp[1][6]=48,另外7,8也只有这一件物品填。所以还是一样的。

    接下来掉第二个物品,掉下1这个物品了,1的价值是7,也就是temp[2][1] = 7。后面一直到temp[2][5]都是等于7。 重点重点来了,到了temp[2][6]的时候怎么办呢?我们的当然一看就是,我要选第一件物品,它的价值是48,可是选了第一件物品,背包就满了,就不能装第二件重量为1的物品了,所以temp[2][6] = 48。

    我们人可以这样思考,关键就来了,关键就是怎么让计算机也可以这样思考呢,我们就需要用代码。其实仔细想想,我掉第二件物品了,判断如果不能装下,那么temp[2][j] = temp[2][j-1] //记住j表示的是我背包现在最大只能装j这么多,那既然这个物品装不下,那么当然不能装了。如果我当前物品重量小于j,那么我就可以选择是装还是不装呢?只要比较装还是不装哪个价值大就行了。如果不装的话价值这个时候的最大价值是不会变的,因为都不装嘛,也就是,temp[2][j] = temp[2-1][j] 。如果我装的话,关键是这个,还是到刚才的到第二件物品的价值为6的时候考虑,如果我装下重量1这个物品,temp[2][6] = temp[2-1][6 - 这个物品的重量] + 物品的价值 //

    其实我 temp[2-1][6-这个物品重量]表示我还没装这个物品之前的价值腾出装这个物品的空间,然后加上这个物品的价值进行比较。关键是之前的每一个状态都用数组给记录下来了。关键代码先看一下,结合代码再理解

    for(int i=1;i<6;i++) {
        for(int j=1;j<9;j++) {
            if(w[i]<=j) {
                temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]); //其实就是比较物品选还是不选哪种价值大。
            }else {
                temp[i][j] = temp[i-1][j];//第i件物品不能放
            }
        }
    }
    

    3.代码示例

    
    import java.util.Scanner;
    
    public class knapsack {
    	static int[] w = new int[6];//每件物品的重量
    	static int[] v = new int[6];//每件物品的价值
    	public static void solution(){
    		
    		
    		int[][] temp = new int[6][9];//8表示背包最多能放8公斤的重量
    		for(int j = 0;j < 9;j++){//初始化每一行
    			temp[0][j] = 0;
    		}
    		for(int i = 1;i < 6;i++){//背包重量为0时,最大价值肯定是0
    			temp[i][0] = 0;
    		}
    		
    		for(int i = 1;i < 6;i++){//从第一个物品开始选,记录我选了前面出现的物品,背包重量从1-8的能选上的最大值
    			for(int j = 1;j < 9;j++){//当i循环到最后一层5的时候,也就是得到了,我5件物品都选上的时候的最大值
    				if(w[i] <= j){//重量比这个状态小,那么就能放。就是放与不放的问题,观察室放重量大还是不放重量大
    					temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]);
    				}else{
    					temp[i][j] = temp[i-1][j];//第i件物品不能放
    				}
    			}
    		}
    		for(int i = 0;i < 6;i++){
    			for(int j = 0;j < 9;j++){
    				System.out.print(temp[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    	public static void main(String[] args) {
    		System.out.println("请依次输入重量和价值:");
    		Scanner scn = new Scanner(System.in);
    		for (int i = 0; i < 6; i++) {
    			w[i] = scn.nextInt();//输入重量
    			v[i] = scn.nextInt();//输入价值
    		}
    		solution();
    		
    		
    		
    	}
    }
    
    
    展开全文
  • 0/1背包问题是学习动态规划算法最经典的例子 Java代码实现0/1背包问题 代码里有详细的注释,比较好理解
  • 0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?分析一波,面对每个物品,我们只有选择拿取或者不拿两...

    0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。

    问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

    分析一波,面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入同一物品多次。

    解决办法:声明一个 大小为  m[n][c] 的二维数组,m[ i ][ j ] 表示 在面对第 i 件物品,且背包容量为  j 时所能获得的最大价值 ,那么我们可以很容易分析得出 m[i][j] 的计算方法,

    (1). j < w[i] 的情况,这时候背包容量不足以放下第 i 件物品,只能选择不拿

    m[ i ][ j ] = m[ i-1 ][ j ]

    (2). j>=w[i] 的情况,这时背包容量可以放下第 i 件物品,我们就要考虑拿这件物品是否能获取更大的价值。

    如果拿取,m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品,背包容量为j-w[i]时的最大价值,也是相当于为第i件物品腾出了w[i]的空间。

    如果不拿,m[ i ][ j ] = m[ i-1 ][ j ] , 同(1)

    究竟是拿还是不拿,自然是比较这两种情况那种价值最大。

    由此可以得到状态转移方程:

    if(j>=w[i])

    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

    else

    m[i][j]=m[i-1][j];

    例:0-1背包问题。在使用动态规划算法求解0-1背包问题时,使用二维数组m[i][j]存储背包剩余容量为j,可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制

    价值数组v = {8, 10, 6, 3, 7, 2},

    重量数组w = {4, 6, 2, 2, 5, 1},

    背包容量C = 12时对应的m[i][j]数组。

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    1

    0

    0

    0

    8

    8

    8

    8

    8

    8

    8

    8

    8

    2

    0

    0

    0

    8

    8

    10

    10

    10

    10

    18

    18

    18

    3

    0

    6

    6

    8

    8

    14

    14

    16

    16

    18

    18

    24

    4

    0

    6

    6

    9

    9

    14

    14

    17

    17

    19

    19

    24

    5

    0

    6

    6

    9

    9

    14

    14

    17

    17

    19

    21

    24

    6

    2

    6

    8

    9

    11

    14

    16

    17

    19

    19

    21

    24

    (第一行和第一列为序号,其数值为0)

    如m[2][6],在面对第二件物品,背包容量为6时我们可以选择不拿,那么获得价值仅为第一件物品的价值8,如果拿,就要把第一件物品拿出来,放第二件物品,价值10,那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10;依次类推,得到m[6][12]就是考虑所有物品,背包容量为C时的最大价值。

    #include 

    #include 

    using namespace std;

    const int N=15;

    int main()

    {

    int v[N]={0,8,10,6,3,7,2};

    int w[N]={0,4,6,2,2,5,1};

    int m[N][N];

    int n=6,c=12;

    memset(m,0,sizeof(m));

    for(int i=1;i<=n;i++)

    {

    for(int j=1;j<=c;j++)

    {

    if(j>=w[i])

    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);

    else

    m[i][j]=m[i-1][j];

    }

    }

    for(int i=1;i<=n;i++)

    {

    for(int j=1;j<=c;j++)

    {

    cout<

    }

    cout<

    }

    return 0;

    }

    到这一步,可以确定的是可能获得的最大价值,但是我们并不清楚具体选择哪几样物品能获得最大价值。

    另起一个 x[ ] 数组,x[i]=0表示不拿,x[i]=1表示拿。

    m[n][c]为最优值,如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样,则x[n]=0 ; 否则 x[n]=1。当x[n]=0时,由x[n-1][c]继续构造最优解;当x[n]=1时,则由x[n-1][c-w[i]]继续构造最优解。以此类推,可构造出所有的最优解。(这段全抄算法书,实在不知道咋解释啊。。)

    void traceback()

    {

    for(int i=n;i>1;i--)

    {

    if(m[i][c]==m[i-1][c])

    x[i]=0;

    else

    {

    x[i]=1;

    c-=w[i];

    }

    }

    x[1]=(m[1][c]>0)?1:0;

    }

    展开全文
  • 举例,背包大小为10,物品有3个,重量和价值,分别是:3,4 4,5 5,6 第一次,放3,4,则数组从a[0]到a[10]分别是: 0 0 0 4 4 4 4 4 4 4 4 第二次,放4,5,分别是 0 0 0 4 5 5 5 9 9 9 9 第三次,放5,6,分别是 0 0 0...

    国际惯例,先上代码,粗略分析:

    package com.bag;

    /**

    * Author: lihao

    * Date:2017/8/31

    * Description:

    */

    public class Main {

    static int totalweight= 150;

    static int N= 5;

    static int values[] = {60, 20, 10, 60, 100};

    static int weights[] = {20, 30, 50, 60, 80};

    public static void main(String[] args) {

    System.out.println(bagProblem(N-1,totalweight));

    bag01();

    }

    //递归实现

    // i {处理到第i件物品} , j{剩余的空间为j}

    public static int bagProblem(int i, int j) {

    int r = 0;

    if(i==-1){

    return 0;

    }

    //如果剩余空间大于所放的物品

    if (j>=weights[i]){

    int r1 = bagProblem(i-1,j-weights[i]) + values[i]; //放第i件

    int r2 = bagProblem(i-1,j);//不放第i件

    r = Math.max(r1,r2);

    }

    return r;

    }

    //非递归

    public static void bag01(){

    int f[] = new int[totalweight+1];

    for (int f1:f){

    f1 = 0;

    }

    for (int i=0;i

    int w = weights[i];

    int v = values[i];

    for (int j= totalweight;j>=w;j--){

    f[j] = Math.max(f[j],f[j-w]+v);

    }

    }

    System.out.println(f[totalweight]);

    }

    }

    递归实现思路:

    重点是寻找状态转移方程

    intr1 = bagProblem(i-1,j-weights[i]) + values[i]; //放第i件intr2 = bagProblem(i-1,j);//不放第i件r = Math.max(r1,r2);

    非递归实现思想:

    建立0-totalweights共total+1大小的数组,用来存放价值。

    第一步,先任意拿一个物品,进行遍历存放。

    第二步,拿第二个物品,进行存放并且和之前的数据进行对比。存放大值。

    以此类推,直至循环完成,取最后一个值,即为最大值。

    举例,背包大小为10,物品有3个,重量和价值,分别是:3,4 4,5 5,6

    第一次,放3,4,则数组从a[0]到a[10]分别是:

    0 0 0 4 4 4 4 4 4 4 4

    第二次,放4,5,分别是

    0 0 0 4 5 5 5 9 9 9  9

    第三次,放5,6,分别是

    0 0 0 4 5 6 6 9 10 11 11

    循环完毕,a[10] = 11。

    展开全文
  • 动态规划算法: 动态规划算法介绍: 动态规划算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获得最优解的处理算法。...动态规划算法最佳实践:背包问题 有一个背包,容量为4磅,现有如下物品 :
  • 对一个实际的背包问题,分别采用动态规划法和回溯法,以动态图ppt的形式生动形象地展示这两种算法的原理和求解过程
  • 01背包问题优化与java代码的详解(动态规划

    千次阅读 多人点赞 2017-11-15 23:26:16
    由于算法讲解文字较多,直接摘图,撰写本文的目的在于写出我对代码的详细解读。如有错误,请大家指出。...//0-1背包问题(跳跃点) /*p用于保存所有可能的最优值 * 设题目为w={2,2,6,5,4};v={6,3,5,4,6
  • 01背包问题的目标是使背包中物品的价值最大。约束条件有两个:一是物品的重量不能超出背包的容量。二是物品只能整体放入背包,不能部分放入。 问题分析 (1)最优子结构 反证法 设(y1,y2,……,yn)是所给01背包问题...
  • 动态规划问题——0/1背包问题(Java实现)

    万次阅读 多人点赞 2018-05-09 11:13:12
    1、问题描述0-1背包问题: 给定N件物品和一个容量为V的背包。放入第i件物品耗费的空间为C[i] ,得到的价值是 W[i] 。 问:哪些物品装入背包可使价值总和最大?最大是多少?2、基本思路2.1 基本思路 这是最基础...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼0-1背包问题java动态规划如题,代码如下public class dongtaiguihua01{public static void main(String []args){int W=10;//背包的总重量int []w= {2,2,6,5,4};//...
  • 简单介绍了动态规划算法,详细分析了01背包问题
  • 0-1背包问题动态规划算法java实现

    千次阅读 2018-12-01 15:51:54
    1 算法实现 import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.Scanner;... // 记录背包的总容量 public int packageweight; // 记录商品总数 publi...
  • 动态规划有很多问题 百度百科: " 动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。...背包问题01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等...
  • 01背包问题java,动态规划

    千次阅读 2018-03-25 21:49:51
    一、问题描述:(01背包即每个物品最多放一个)01 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?二、...
  • 先不要深琢算法的思想,也可以看一下,不懂也没事,然后再找这个算法能解决的一些具体的场景,应用动态规划的场景就多了去了,比如什么最长公共子序列问题,爬楼梯,矩阵连乘,还有比较复杂的股票问题,再就是我这篇...
  • 2)与分治法不同的是,动态规划法用于求解经分解得到子问题不是相互独立的,即下一个子问题的求解是建立在上一个子问题的解的基础上,进行下一步求解。 3)动态规划法可以通过填表的方式逐步推进,得到最优解 2.0-1...
  • 动态规划算法一、基本概念二、算法步骤及问题举例三、动态规划解决0/1背包问题代码实现 一、基本概念 动态规划算法的核心思想是:将大问题划分为小问题进行解决,从而一步一步获得最优解的处理算法。 动态规划算法...
  • 当可以放入前2件物品即i=1时,我们需要进行这样的处理:若j=w[1]时,假设此时背包容量j=8,第二件物品可以被放入背包内,那么便会出现两种情况:(1)将第二件物品放入背包,那么背包中物品的最大价值是多少呢?...
  • 问题描述: 现有一个容量为VVV的背包,以及nnn件物品,其分别占据的容量为cic_ici​ ,其分别带来的价值为wiw_iwi​,(i=1,2,...,ni={...使用动态规划进行求解: 子问题定义状态: dp[i][j]dp[i][j]dp[i][j]表示 前...
  • 动态规划01背包问题 /* 问题描述: 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和 eg:number = 4 ; capacity = 8 ; i 物体编号 1 2 3 4 w(体积) 2 3 4 5 v...
  • 问题描述:给定n种物品和一背包。物品i的重量是wi,体积是vi,其价值是vi,背包容量c,背包体积为d。问如何选择装入背包中的物品,使得装入背包中物品的总价值最大?在选择装入背包的的物品时,每种物品只有两种选择...
  • P01: 01背包问题题目给定 N 种物品和一个容量为 V 的背包,物品 i 的体积是 wi,其价值为 ci 。(每种物品只有一个)问:如何选择装入背包的物品,使得装入背包中的物品的总价值最大?面对每个物品,我们只有选择放入...
  • **问题描述:**给定n种物品和一背包。物品i的重量是wi,体积是bi,其价值为vi,背包的容量为C,容积为D。问:应该如何选择装人...试设计一个解此问题动态规划算法,并分析算法的计算复杂性。 问题分析: m(i,j,k)是背...
  • 背包问题(Knapsack problem)是一种组合优化的NP完全问题问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
  • 01背包问题背包问题的区别在于,01背包,物品的选择只有两种一种是拿,另一种是不拿,而背包问题在于,物品可以只取一部分。所以01背包问题不能用贪心算法解决。 以dp[i][j]表示用i种物品,重量为j表示所取得的...
  • 根据提示信息输入要测试的数据文件的编号(1-5),数据文件中第一行分别为背包容量和物品个数,第二行为物品重量,第三行为物品价值,用" "分隔(如:1 2 3)。输入数据文件的编号后程序开始运行,依次输出背包总...
  • 算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
  • * 0-1背包问题:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高 * * 以下用一个问题作为案例 * 挖矿问题 * 5座金矿,每座金矿的储量不同,需要参与...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,128
精华内容 8,851
关键字:

01背包问题动态规划java

java 订阅