菜单

betway体育算法笔记_019:背包问题(Java)算法笔记_019:背包问题(Java)

2018年9月19日 - betway体育

目录

1 style=”font-family: 宋体;”>问题讲述

2 style=”font-family: 宋体;”>解决方案

2.1
蛮力法

style=”font-size: 18px;”>2.2
减治法

2.2.1 style=”font-family: 宋体;”>递归求解

2.2.2 style=”font-family: 宋体;”>非递归求解(运用异或运算)

style=”font-size: 18px;”>2.3
动态规划法

目录

1 style=”font-family: 宋体;”>问题讲述

2 style=”font-family: 宋体;”>解决方案

2.1
蛮力法

style=”font-size: 18px;”>2.2
减治法

2.2.1 style=”font-family: 宋体;”>递归求解

2.2.2 style=”font-family: 宋体;”>非递归求解(运用异或运算)

style=”font-size: 18px;”>2.3
动态规划法

 


 


1 问题讲述

为定n个轻重为w1,w2,w3,…,wn,价值也v1,v2,…,vn的品与一个承重为W的背包,求这些物品中极有价之子集(PS:每一个物品要选择同差,要么不选择),并且使能装到背包。

附形象描述:就比如一个小偷打算将最好有价之赃装他的背包一样,但要是大家不喜扮小偷的角色,也足以想像吗同样绑架运输机打算将最好有价之品运输及异乡,同时这些物品的份量不能够超出其的运输能力。

1 问题讲述

于定n个轻重也w1,w2,w3,…,wn,价值吗v1,v2,…,vn的物料与一个承重为W的背包,求这些物品遭极有价的子集(PS:每一个品要捎同坏,要么不拣),并且只要能装到背包。

附形象描述:就像一个小偷打算将极有价的赃装他的背包一样,但如果大家不爱好扮小偷的角色,也堪设想为同样绑架运输机打算将极有价之物品运输至异乡,同时这些物料的重量不克超过其的运输能力。

 


 


2 解决方案

2 解决方案

2.1 蛮力法

采用蛮力法解决带有n个物品的背包问题,首先得告来就n个物品的有着子集,对于各级一个物品在个别种状态:选中(在程序中因故1表示),未当选(在次中用0表示)。该n个物品的所有子集数数量为2^n。下面请圈一个略示例:

 betway体育 1

这边,使用一个二维数组存放有子集,数组的各个一行代表一个子集,每一样排列代表一个有血有肉物品。

package com.liuzhen.chapterThree;

public class Knapsack {

    public int maxSumValue = 0;        //定义满足背包问题子集的最大承重所得的总价值,初始化为0
    /*
     * 数组A的行数为2^n,代表n个物品共有2^n个子集,列数为n。即每一行的排列为一个背包实例
     * 数组weight存放每个物品的具体重量
     * 数组value存放每个物品的具体价值
     * n代表共有n个物品
     * maxWeight表示背包最大承重量
     */
    public void bruteForce(int[][] A,int[] weight,int[] value,int n,int maxWeight){

        for(int i = 0;i < Math.pow(2, n);i++){  //总共有2^n个子集,需要进行2^n次循环,及数组A有2^n行
            int temp1 = i;
            for(int j = 0;j < n;j++){    //数组A有n列,每一列代表一个物品
                int temp2 = temp1%2;
                A[i][j] = temp2;
                temp1 = temp1/2;
            }
        }

        printArray(A,weight,value,maxWeight);

    }

    //输出穷举方案的背包实例的选择物品(0代表不包含该物品,1表示包含该物品)的总重量及总价值,并输出最优实例的总价值
    public void printArray(int[][] A,int[] weight,int[] value,int maxWeight){
        int len1 = A.length;         //二维数组的行数
        int len2 = A[0].length;      //二维数组的列数
        for(int i = 0;i < len1;i++){
            int tempWeight = 0;      //暂时计算当前选中背包实例物品的总重量,初始化为0
            int tempSumValue = 0;    //暂时计算当前选中背包实例物品的总价值,初始化为0
            for(int j = 0;j < len2;j++){
                System.out.print(A[i][j]+" ");
//                if(A[i][j] != 0)
//                    System.out.print(" 物品"+j);
                tempWeight += A[i][j]*weight[j];
                tempSumValue += A[i][j]*value[j];
            }
            System.out.print("\t"+"总重量为:"+tempWeight);
            if(tempWeight <= maxWeight)
                System.out.print("\t"+"总价值为:"+tempSumValue);
            else
                System.out.print("\t"+"不可行(超出背包最大承重)");
            if(tempWeight <= maxWeight && tempSumValue > maxSumValue)
                maxSumValue = tempSumValue;
            System.out.println();
        }
        System.out.println("穷举查找得知,最优解的总价值为:"+maxSumValue);
    }

    public static void main(String[] args){
        Knapsack test = new Knapsack();
        int[][] A = new int[16][4];
        int[] weight = {7,3,4,5};
        int[] value = {42,12,40,25};
        test.bruteForce(A,weight,value,4,10);      //背包的承重最大为10
    }

}

运作结果:

0 0 0 0     总重量为:0    总价值为:0
1 0 0 0     总重量为:7    总价值为:42
0 1 0 0     总重量为:3    总价值为:12
1 1 0 0     总重量为:10    总价值为:54
0 0 1 0     总重量为:4    总价值为:40
1 0 1 0     总重量为:11    不可行(超出背包最大承重)
0 1 1 0     总重量为:7    总价值为:52
1 1 1 0     总重量为:14    不可行(超出背包最大承重)
0 0 0 1     总重量为:5    总价值为:25
1 0 0 1     总重量为:12    不可行(超出背包最大承重)
0 1 0 1     总重量为:8    总价值为:37
1 1 0 1     总重量为:15    不可行(超出背包最大承重)
0 0 1 1     总重量为:9    总价值为:65
1 0 1 1     总重量为:16    不可行(超出背包最大承重)
0 1 1 1     总重量为:12    不可行(超出背包最大承重)
1 1 1 1     总重量为:19    不可行(超出背包最大承重)
穷举查找得知,最优解的总价值为:65

 

2.1 蛮力法

采用蛮力法解决带有n个物品的背包问题,首先得请出立即n个物品的装有子集,对于各一个品有个别栽状况:选中(在次中之所以1意味),未入选(在次中用0表示)。该n个物品的所有子集数数量为2^n。下面请看一个简便示例:

 betway体育 2

此,使用一个二维数组存放有子集,数组的诸一行代表一个子集,每一样排列代表一个现实物品。

package com.liuzhen.chapterThree;

public class Knapsack {

    public int maxSumValue = 0;        //定义满足背包问题子集的最大承重所得的总价值,初始化为0
    /*
     * 数组A的行数为2^n,代表n个物品共有2^n个子集,列数为n。即每一行的排列为一个背包实例
     * 数组weight存放每个物品的具体重量
     * 数组value存放每个物品的具体价值
     * n代表共有n个物品
     * maxWeight表示背包最大承重量
     */
    public void bruteForce(int[][] A,int[] weight,int[] value,int n,int maxWeight){

        for(int i = 0;i < Math.pow(2, n);i++){  //总共有2^n个子集,需要进行2^n次循环,及数组A有2^n行
            int temp1 = i;
            for(int j = 0;j < n;j++){    //数组A有n列,每一列代表一个物品
                int temp2 = temp1%2;
                A[i][j] = temp2;
                temp1 = temp1/2;
            }
        }

        printArray(A,weight,value,maxWeight);

    }

    //输出穷举方案的背包实例的选择物品(0代表不包含该物品,1表示包含该物品)的总重量及总价值,并输出最优实例的总价值
    public void printArray(int[][] A,int[] weight,int[] value,int maxWeight){
        int len1 = A.length;         //二维数组的行数
        int len2 = A[0].length;      //二维数组的列数
        for(int i = 0;i < len1;i++){
            int tempWeight = 0;      //暂时计算当前选中背包实例物品的总重量,初始化为0
            int tempSumValue = 0;    //暂时计算当前选中背包实例物品的总价值,初始化为0
            for(int j = 0;j < len2;j++){
                System.out.print(A[i][j]+" ");
//                if(A[i][j] != 0)
//                    System.out.print(" 物品"+j);
                tempWeight += A[i][j]*weight[j];
                tempSumValue += A[i][j]*value[j];
            }
            System.out.print("\t"+"总重量为:"+tempWeight);
            if(tempWeight <= maxWeight)
                System.out.print("\t"+"总价值为:"+tempSumValue);
            else
                System.out.print("\t"+"不可行(超出背包最大承重)");
            if(tempWeight <= maxWeight && tempSumValue > maxSumValue)
                maxSumValue = tempSumValue;
            System.out.println();
        }
        System.out.println("穷举查找得知,最优解的总价值为:"+maxSumValue);
    }

    public static void main(String[] args){
        Knapsack test = new Knapsack();
        int[][] A = new int[16][4];
        int[] weight = {7,3,4,5};
        int[] value = {42,12,40,25};
        test.bruteForce(A,weight,value,4,10);      //背包的承重最大为10
    }

}

运作结果:

0 0 0 0     总重量为:0    总价值为:0
1 0 0 0     总重量为:7    总价值为:42
0 1 0 0     总重量为:3    总价值为:12
1 1 0 0     总重量为:10    总价值为:54
0 0 1 0     总重量为:4    总价值为:40
1 0 1 0     总重量为:11    不可行(超出背包最大承重)
0 1 1 0     总重量为:7    总价值为:52
1 1 1 0     总重量为:14    不可行(超出背包最大承重)
0 0 0 1     总重量为:5    总价值为:25
1 0 0 1     总重量为:12    不可行(超出背包最大承重)
0 1 0 1     总重量为:8    总价值为:37
1 1 0 1     总重量为:15    不可行(超出背包最大承重)
0 0 1 1     总重量为:9    总价值为:65
1 0 1 1     总重量为:16    不可行(超出背包最大承重)
0 1 1 1     总重量为:12    不可行(超出背包最大承重)
1 1 1 1     总重量为:19    不可行(超出背包最大承重)
穷举查找得知,最优解的总价值为:65

 

2.2 减治法

2.2 减治法

2.2.1 递归求解

背包问题之面目是求取n个不同物品的有所子集,在这个基础及探寻重量合适,总价值最充分之子集。此处就叫起什么求出n个不同物品的富有子集实现,至于哪些寻找适合背包问题之子集,感兴趣之同桌可以自己下手实现以下哟~

此处是行使减治法思想,根据二进制反射格雷码的算法思想,来实现这个题材。具体讲,请看下一段出自《算法设计以及析基础》第三版本及教:

 betway体育 3

切切实实代码如下:

package com.liuzhen.chapter4;

import java.util.LinkedList;
import java.util.List;

public class GrayCode {
    //递归求取n个不同物品的所有子集
    public String[] getGrayCode2(int n){
        int len = (int) Math.pow(2, n);
        String[] result = new String[len];
        if(n == 1){
            result[0] = "0";
            result[1] = "1";
            return result;
        }
        String[] temp = getGrayCode2(n-1);               //递归求取n-1个不同物品的所有子集
        for(int i = 0;i < temp.length;i++){        //根据格雷码去掉最高位,前一半和后一半二进制数完全一样的对称性
            result[i] = "0" + temp[i];         //前一半格雷码,最高位为0
            result[result.length-1-i] = "1" + temp[i];   //后一半格雷码,最高位为1      
        }
        return result;
    }

    public static void main(String[] args){
        GrayCode test = new GrayCode();
        String[] temp2 = test.getGrayCode2(3);
        System.out.println("使用递归求解n个物品所有子集结果如下:");
        for(int i = 0;i < temp2.length;i++)
            System.out.println(temp2[i]);
    }
}

运作结果:

使用递归求解n个物品所有子集结果如下:
000
001
011
010
110
111
101
100

 

2.2.1 递归求解

背包问题之真相是求取n个不同物品的保有子集,在此基础及搜索重量合适,总价值最特别之子集。此处就叫出什么样求出n个不同物品的装有子集实现,至于何以寻找可背包问题的子集,感兴趣的同桌可以团结下手实现以下哟~

此是应用减治法思想,根据二进制反射格雷码的算法思想,来落实者题材。具体讲,请看下面一段落出自《算法设计以及分析基础》第三本子上教学:

 betway体育 4

切切实实代码如下:

package com.liuzhen.chapter4;

import java.util.LinkedList;
import java.util.List;

public class GrayCode {
    //递归求取n个不同物品的所有子集
    public String[] getGrayCode2(int n){
        int len = (int) Math.pow(2, n);
        String[] result = new String[len];
        if(n == 1){
            result[0] = "0";
            result[1] = "1";
            return result;
        }
        String[] temp = getGrayCode2(n-1);               //递归求取n-1个不同物品的所有子集
        for(int i = 0;i < temp.length;i++){        //根据格雷码去掉最高位,前一半和后一半二进制数完全一样的对称性
            result[i] = "0" + temp[i];         //前一半格雷码,最高位为0
            result[result.length-1-i] = "1" + temp[i];   //后一半格雷码,最高位为1      
        }
        return result;
    }

    public static void main(String[] args){
        GrayCode test = new GrayCode();
        String[] temp2 = test.getGrayCode2(3);
        System.out.println("使用递归求解n个物品所有子集结果如下:");
        for(int i = 0;i < temp2.length;i++)
            System.out.println(temp2[i]);
    }
}

运行结果:

使用递归求解n个物品所有子集结果如下:
000
001
011
010
110
111
101
100

 

2.2.2 非递归求解(运用异或运算)

此为以求取格雷码的思,完成求取n个物品的装有子集,不过此是行使非递归来实现,运用异或运算,其布局十分抢眼,个人感觉要明白这种编码方式和揣摩得多么运用,直至熟能生巧。

切切实实代码如下:

package com.liuzhen.chapter4;

import java.util.LinkedList;
import java.util.List;

public class GrayCode {
    //运用异或运算得到n个不同物品的所有子集
    public List<Integer> getGaryCode1(int n){
        List<Integer> result = new LinkedList<>();
        if(n >= 0){
            result.add(0);
            int top = 1;
            for(int i = 0;i < n;i++){
                System.out.print("result.size() = "+result.size()+"  ");
                for(int j = result.size()-1;j >= 0;j--){
                    System.out.print("result.get("+j+")^top = "+result.get(j)+"^"+top+" = "+(result.get(j)^top)+"  ");
                    result.add(result.get(j)^top);   //符号‘^’是异或运算(使用具体数字的二进制进行运算),即1^0=1,0^1=1,0^0=0,1^1=0
                }
                System.out.println();
                top <<= 1;         //top二进制左移1位,相当于top=top*2
                System.out.println("top = "+top);
            }
        }
        return result;
    }
    //把十进制数转换成长度为n的二进制数
    public StringBuffer[] getBinary(List<Integer> A,int n){
        StringBuffer[] result = new StringBuffer[A.size()];
        for(int i = 0;i < A.size();i++){
            int temp1 = A.get(i);
            int judge = n;
            char[] temp2 = new char[n];     //用于存放temp1的n位二进制数
            while(judge > 0){
                int temp3 = temp1%2; 
                temp2[judge-1] = (char) (temp3+48);  //对照char的unicode编码,把int型数字转换为char型
                temp1 = temp1/2;
                judge--;    
            }
            result[i] = new StringBuffer(String.valueOf(temp2));
        }
        return result;
    }

    public static void main(String[] args){
        GrayCode test = new GrayCode();
        List<Integer> temp = test.getGaryCode1(3);
        System.out.println(temp);
        StringBuffer[] temp1 = test.getBinary(temp, 3);
        for(int i = 0;i < temp1.length;i++)
            System.out.println(temp1[i]);
    }
}

运作结果:

result.size() = 1  result.get(0)^top = 0^1 = 1  
top = 2
result.size() = 2  result.get(1)^top = 1^2 = 3  result.get(0)^top = 0^2 = 2  
top = 4
result.size() = 4  result.get(3)^top = 2^4 = 6  result.get(2)^top = 3^4 = 7  result.get(1)^top = 1^4 = 5  result.get(0)^top = 0^4 = 4  
top = 8
[0, 1, 3, 2, 6, 7, 5, 4]
000
001
011
010
110
111
101
100

 

2.2.2 非递归求解(运用异或运算)

这里为使求取格雷码的考虑,完成求取n个物品的备子集,不过此是运用非递归来实现,运用异或运算,其结构十分巧妙,个人感觉要明了这种编码方式和思得多运用,直至熟能生巧。

切切实实代码如下:

package com.liuzhen.chapter4;

import java.util.LinkedList;
import java.util.List;

public class GrayCode {
    //运用异或运算得到n个不同物品的所有子集
    public List<Integer> getGaryCode1(int n){
        List<Integer> result = new LinkedList<>();
        if(n >= 0){
            result.add(0);
            int top = 1;
            for(int i = 0;i < n;i++){
                System.out.print("result.size() = "+result.size()+"  ");
                for(int j = result.size()-1;j >= 0;j--){
                    System.out.print("result.get("+j+")^top = "+result.get(j)+"^"+top+" = "+(result.get(j)^top)+"  ");
                    result.add(result.get(j)^top);   //符号‘^’是异或运算(使用具体数字的二进制进行运算),即1^0=1,0^1=1,0^0=0,1^1=0
                }
                System.out.println();
                top <<= 1;         //top二进制左移1位,相当于top=top*2
                System.out.println("top = "+top);
            }
        }
        return result;
    }
    //把十进制数转换成长度为n的二进制数
    public StringBuffer[] getBinary(List<Integer> A,int n){
        StringBuffer[] result = new StringBuffer[A.size()];
        for(int i = 0;i < A.size();i++){
            int temp1 = A.get(i);
            int judge = n;
            char[] temp2 = new char[n];     //用于存放temp1的n位二进制数
            while(judge > 0){
                int temp3 = temp1%2; 
                temp2[judge-1] = (char) (temp3+48);  //对照char的unicode编码,把int型数字转换为char型
                temp1 = temp1/2;
                judge--;    
            }
            result[i] = new StringBuffer(String.valueOf(temp2));
        }
        return result;
    }

    public static void main(String[] args){
        GrayCode test = new GrayCode();
        List<Integer> temp = test.getGaryCode1(3);
        System.out.println(temp);
        StringBuffer[] temp1 = test.getBinary(temp, 3);
        for(int i = 0;i < temp1.length;i++)
            System.out.println(temp1[i]);
    }
}

运转结果:

result.size() = 1  result.get(0)^top = 0^1 = 1  
top = 2
result.size() = 2  result.get(1)^top = 1^2 = 3  result.get(0)^top = 0^2 = 2  
top = 4
result.size() = 4  result.get(3)^top = 2^4 = 6  result.get(2)^top = 3^4 = 7  result.get(1)^top = 1^4 = 5  result.get(0)^top = 0^4 = 4  
top = 8
[0, 1, 3, 2, 6, 7, 5, 4]
000
001
011
010
110
111
101
100

 

2.3 动态规划法

此处编码思想主要参照自《算法设计和分析基础》第三本的一律段子讲解,具体如下:

 betway体育 5

betway体育 6

betway体育 7

切切实实代码如下:

package com.liuzhen.chapter8;

public class MFKnapsack {
    /*
     * 参数weight:物品1到物品n的重量,其中weight[0] = 0
     * 参数value:物品1到物品n的价值,其中value[0] = 0
     * 函功能:返回背包重量从0到所有物品重量之和区间的每一个重量所能达到的最大价值
     */
    public int[][] getMaxValue(int[] weight, int[] value) {
        int lenRow = weight.length;
        int lenColumn = 0;
        for(int i = 0;i < weight.length;i++)
            lenColumn += weight[i];
        int[][] F = new int[lenRow][lenColumn+1]; //列值长度加1,是因为最后一列要保证重量值为lenColumn  
        for(int i = 1;i < weight.length;i++) {
            for(int j = 1;j <= lenColumn;j++) {
                if(j < weight[i])
                    F[i][j] = F[i-1][j];
                else {
                    if(F[i-1][j] > F[i-1][j-weight[i]] + value[i])
                        F[i][j] = F[i-1][j];
                    else 
                        F[i][j] = F[i-1][j-weight[i]] + value[i];
                }
            }
        }
        return F;
    }

    public static void main(String[] args) {
        MFKnapsack test = new MFKnapsack();
        int[] weight = {0,2,1,3,2};
        int[] value = {0,12,10,20,15};
        int[][] F = test.getMaxValue(weight, value);
        System.out.println("背包承重从0到所有物品重量之和为8的承重能够达到的最大价值分别为:");
        for(int i = 0;i < F.length;i++) {
            for(int j = 0;j < F[0].length;j++) 
                System.out.print(F[i][j]+"\t");
            System.out.println();
        }
    }
}

 

运转结果:

背包承重从0到所有物品重量之和为8的承重能够达到的最大价值分别为:
0    0    0    0    0    0    0    0    0    
0    0    12    12    12    12    12    12    12    
0    10    12    22    22    22    22    22    22    
0    10    12    22    30    32    42    42    42    
0    10    15    25    30    37    45    47    57    

 

 

参考资料:

     1. java实现格雷码生成

   
 2.背包问题九谈话

      3.《算法设计和分析基础》第3本子   Anany Levitin
著   潘彦 译

 

2.3 动态规划法

这里编码思想要参照自《算法设计及分析基础》第三版本的同一段讲解,具体如下:

 betway体育 8

betway体育 9

betway体育 10

现实代码如下:

package com.liuzhen.chapter8;

public class MFKnapsack {
    /*
     * 参数weight:物品1到物品n的重量,其中weight[0] = 0
     * 参数value:物品1到物品n的价值,其中value[0] = 0
     * 函功能:返回背包重量从0到所有物品重量之和区间的每一个重量所能达到的最大价值
     */
    public int[][] getMaxValue(int[] weight, int[] value) {
        int lenRow = weight.length;
        int lenColumn = 0;
        for(int i = 0;i < weight.length;i++)
            lenColumn += weight[i];
        int[][] F = new int[lenRow][lenColumn+1]; //列值长度加1,是因为最后一列要保证重量值为lenColumn  
        for(int i = 1;i < weight.length;i++) {
            for(int j = 1;j <= lenColumn;j++) {
                if(j < weight[i])
                    F[i][j] = F[i-1][j];
                else {
                    if(F[i-1][j] > F[i-1][j-weight[i]] + value[i])
                        F[i][j] = F[i-1][j];
                    else 
                        F[i][j] = F[i-1][j-weight[i]] + value[i];
                }
            }
        }
        return F;
    }

    public static void main(String[] args) {
        MFKnapsack test = new MFKnapsack();
        int[] weight = {0,2,1,3,2};
        int[] value = {0,12,10,20,15};
        int[][] F = test.getMaxValue(weight, value);
        System.out.println("背包承重从0到所有物品重量之和为8的承重能够达到的最大价值分别为:");
        for(int i = 0;i < F.length;i++) {
            for(int j = 0;j < F[0].length;j++) 
                System.out.print(F[i][j]+"\t");
            System.out.println();
        }
    }
}

 

运转结果:

背包承重从0到所有物品重量之和为8的承重能够达到的最大价值分别为:
0    0    0    0    0    0    0    0    0    
0    0    12    12    12    12    12    12    12    
0    10    12    22    22    22    22    22    22    
0    10    12    22    30    32    42    42    42    
0    10    15    25    30    37    45    47    57    

 

 

参考资料:

     1. java实现格雷码生成

   
 2.背包问题九张嘴

      3.《算法设计及析基础》第3版本   Anany Levitin
著   潘彦 译

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图