1. 云栖社区>
  2. >
  3. 正文

01背包问题

作者:用户 来源:互联网 时间:2018-09-17 16:15:15

算法01背包

01背包问题 - 摘要: 本文讲的是01背包问题, 参考mu399的专栏:网址http://blog.csdn.net/mu399/article/details/7722810 参考qinyg的博客:网址http://www.cnblogs.com/qinyg/archiv

参考mu399的专栏:网址http://blog.csdn.net/mu399/article/details/7722810

参考qinyg的博客:网址http://www.cnblogs.com/qinyg/archive/2012/04/26/2471829.html




public class ZeroOnePackage {

    //01背包问题,可以分为2个部分,一个为物品可以拆分,另一个为不可以拆分,由于可以拆分的简单,这里只介绍不可以拆分的解法
/*
01背包的问题描述为:
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大。

析:
在选择物品的时候,对每种物品只有两种选择,要么装入,要么不装入,因此,此为一个0-1背包问题。
01背包的递归解为:m[i,j]=max{m[i-1,j-wi]+vi,m[i-1,j]},j>=wi
m[i,j]=m[i-1,j] j<wi
m[i,0]=m[0,j]=0

其中,m[i,j]为前i件物品中选择若干件,放入承重为j的背包中,得到的最大的价值
wi为第i件商品的重量
vi为第i件商品的价值

具体例题:
有编号为a,b,c,d,e的五件物品,他们的重量分别为4,5,6,2,2,价值分别为6,4,5,3,6,现在给你一个承重为10的背包,怎么实现价值最大。

表从上向下生成:
name  weight  value  1  2   3   4   5    6  7   8    9    10
 a      4      6     0  0   0   6   6    6  6   6    6     6
 b      5      4     0  0   0   6   6    6  6   6    10    10
 c      6      5     0  0   0   6   6    6  6   6    10    11
 d      2      3     0  3   3   6   6    9  9   9    10    11
 e      2      6     0  6   6   9   9    12 12  15   15    15
 
*/    

    
    public static int max(int para1,int para2){
        if(para1>para2){
            return para1;
        }else{
            return para2;
        }
        
    }
    
    public static int getMaxValue(int n,int weight[],int value[],int state[],int c){
        //n为物品的数量,数组时需要加1,此时可以从0,1,....n个物品,共n+1个商品,其中第0个为虚构的
        //对于物品的价值,可以写成2维数组
        int m[][] = new int[n+1][c+1]; //n为0,1,2,,,,,(n-1),背包重量为0,1,2,,,,C
        int i,j;
        
        for(i=0;i<=n;i++){
            m[i][0]=0;
        }
        for(j=0;j<=c;j++){
            m[0][j]=0;
        }
        
        for(i=1;i<=n;i++){
            //System.out.println();
            for(j=1;j<=c;j++){
                if(j<weight[i]){ //新的物品太重,无法放下
                    m[i][j]=m[i-1][j];
                }else{
                    m[i][j]=max(m[i-1][j-weight[i]]+value[i],m[i-1][j]);
                }
                //System.out.print("m["+i+"]["+j+"]="+m[i][j]+"  ");
                //System.out.print(m[i][j]+"  ");
            }
        }
        
        //根据其最大价值,反向推断是否添加了物品i
        
        j=c;
        for(i=n;i>0;i--){
            if(m[i][j]>m[i-1][j]){//物品i添加到了序列列表
                state[i]=1;
                j=j-weight[i];
            }else{ //没有添加
                state[i]=0;
            }
        }
        
        return m[n][c]; //最大价值
    }
    
    
    
    public static void main(String[] args) {

        int n=5;//5件物品,物品编号为a,b,c,d,e(下面为多加一件物品,第一个物品为虚拟的物品)
        int weight[]={0,4,5,6,2,2};//物品的重量
        int value[]={0,6,4,5,3,6}; //对应物品的价值
        int c=10; //背包容量
        int state[]={0,0,0,0,0,0};//开始状态
        char name[]={' ','a','b','c','d','e'};
        int maxValue=getMaxValue(n,weight,value,state,c);
        System.out.println("最大价值为="+maxValue);
        for(int i=1;i<=5;i++){
            if(state[i]==1){
                System.out.print(name[i]+"  ");
            }
        }
        
        //System.out.println();
    }

}


以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索算法 01背包 ,以便于您获取更多的相关知识。

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

现在注册,免费体验40+云产品,及域名优惠!

云服务器9.9元/月,大学必备