背包问题 订阅
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。 展开全文
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
信息
外文名
Knapsack Problem
提出者
Merkle-Hellman
中文名
背包问题
应用领域
运筹学,应用数学,密码学等
背包问题应用
1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。 [3]  背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, [4]  选择投资和投资组合, [5]  选择资产支持资产证券化 [6]  ,和生成密钥为Merkle-Hellman [7]  和其他背包密码系统。背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。 [8] 
收起全文
精华内容
下载资源
问答
  • 背包问题

    千次阅读 多人点赞 2015-06-22 20:00:05
    背包问题

    背包问题

    .问题重述

    给定n个物品,价值分别是:v1,v2,...,vn,重量分别是:w1,w2,...,wn。现挑选物品放入承重为W的背包,使得背包内物品的价值最大,且背包内物品的总重量小于W.这里假设承重都是正整数。

    .解决方案

    首先我们先设一个量:V[i,j],它代表在前i个物品中进行挑选,能放进承重为j的背包中,背包内物品价值最大的物品挑选组合的价值。

    那根据这个设定的量,我们可以得出这样的一些结论:

    1.若在前i-1个物品中挑选,则最优集合为V[i-1,j],如果在V[i,j]的组合中,背包内是不包括了第i个物品的话,那么V[i,j]=V[i-1,j]

    2.如果在V[i,j]的组合中,背包内是包括了第i个物品的话,则该组合等于V[i-1,j]加上第i个物品,也就是说V[i,j]=V[i-1,j-wi](注意:此处的前提条件是V[i,j]包括了第i个物品)

    所以,我们可以得出计算V[i,j]的公式:

    if j-wi<0

    V[i,j]=V[i-1,j]

    else

    V[i,j]=max{V[i-1,j],vi+V[i-1,j-wi]}

    此外,V[0,j]=V[i,0]=0,即背包内无物品或说背包承重为0时,背包内最大价值都是0.

    有了解决方案的公式,我们就可以进行问题的解决。

    三.示例

    下面根据以上所推公式,我们对一个例子进行演示。

    例子:

    物品 重量 价值
    1 2 12
    2 1 10
    3 3 20
    4 2 15

     背包承重W=5

    那么首先按初始化条件建立表格:

    i/j 0 1 2 3 4 5
    0 0 0 0 0 0 0
    1 0          
    2 0          
    3 0          
    4 0          

    表格可以按行填写,也可以按列填写,本例按列填写。 

    首先,V[1,1]表示在前1个物品中挑选,重量不得超过1,我们发现前一个w1=2>1,所以没有解决方案,即V[1,1]=0;接着,V[2,1]表示在前2个物品中挑选,重量不得超过1,我们发现前一个w2=1,所以有解决方案,为{物品二},即V[2,1]=10;然后,V[3,1]表示在前3个物品中挑选,重量不得超过1,我们发现前一个w3=3>1,所以有解决方案,还是{物品二},即V[3,1]=10;最后,V[4,1]表示在前4个物品中挑选,重量不得超过1,我们发现前一个w4=2>1,所以没有解决方案,即V[4,1]=10;得出下表:

    i/j 0 1 2 3 4 5
    0 0 0 0 0 0 0
    1 0 0        
    2 0 10        
    3 0 10        
    4 0 10        

    接着,填第3列。

    首先,V[1,2]表示在前1个物品中挑选,重量不得超过2,我们发现前一个w1=2,所以有解决方案,为{物品一},即V[1,2]=12;接着,V[2,2]表示在前2个物品中挑选,重量不得超过2,我们发现前一个w2=1<2,且V[1,0]+v2<V[1,2],所以有解决方案,为{物品一},即V[2,2]=12;然后,V[3,2]表示在前3个物品中挑选,重量不得超过2,我们发现前一个w3=3>2,所以有解决方案,还是{物品二},即V[3,2]=12;最后,V[4,2]表示在前4个物品中挑选,重量不得超过2,我们发现前一个w4=2,且V[3,1]+v4>V[3,0],所以有解决方案,为{物品4},即V[4,1]=15;得出下表:

    i/j 0 1 2 3 4 5
    0 0 0 0 0 0 0
    1 0 0 12      
    2 0 10 12      
    3 0 10 12      
    4 0 10 15      

    对以上两个步骤我们可以看出我们可以在表格里得到这样的规律: 

    i/j 0 ... j-wi ... j ... W
    0 0 0 0 0 0 0 0
    ... 0            
    i-1 0   V[i-1,j-wi]   V[i-1,j]    
    i 0       V[i,j]    
    ... 0            
    n 0           目标

    所以从V[1,1]开始逐列填写,最终可得表如下: 

    i/j 0 1 2 3 4 5
    0 0 0 0 0 0 0
    1 0 0 12 12 12 12
    2 0 10 12 22 22 22
    3 0 10 12 22 30 32
    4 0 10 15 25 30 37

    因此,最大价值为V[4,5]=37 

    除了得出最大价值外,我们还想得到组成最大价值的物品,即哪些物品放入了背包,该问题的解决可对已经建好的表格使用回溯法得到。

    首先对目标格V[4,5]开始,判断V[4,5]是否等于V[3,5](也就是向上一格比较),如果相等,就是说明在前3个物品挑选与在前4个物品挑选是一样的,也就说第4个物品没有放入背包里;如果不相等,就是背包里放入的第4个物品。根据例子,发现V[4,5]不等于V[3,5],所以第4个物品被放入了背包;接着看[i-1,j-wi],就是看从3个物品里挑选,背包承重为W-w4的格子——[3,3],比较[3,3][2,3],发现[3,3]=[2,3],所以第3个物品不包括在背包里,也即是从前3个物品挑选与从前2个物品挑选是一样的,所以看[2,3],比较[2,3][2,2],发现[2,3]不等于[1,3],同理,物品2被放入了背包。然后看[1,2]([2-1,3-1])[1,2][0,2]不等,所以物品1被放入了背包,回溯结束,最后的背包里有物品1,物品2,物品4

     

    四.具体算法

    背包问题算法伪代码:

    MFKnapsack(i,j)

    //输入:背包可承受最大物品数i与背包可承受最大重量j

    //输出:背包内物品的最大值

    //V[1,...,n]为物品价值序列,W[1,...,n]为物品重量序列,为全局变量

    if(i~=0&&j~=0)

        if(F(i,j)<0)

            if(j<W(1,i))

                value=MFKnapsack(i-1,j);

            else

                value=max(MFKnapsack(i-1,j),V(1,i)+MFKnapsack(i-1,j-W(1,i)));

    else

    value=0

    return value

     

    FindBag(i,j)

    //输入:背包可承受最大物品数i与背包可承受最大重量j

    //输出:背包内最优子集包含的物品

    if(r(i,j)==r(i-1,j))

          i=i-1;

    else

          s=[s,i];

          j=j-W(1,i);

          i=i-1;  

    return s

     

    下面给出具体程序,用matlab写的m文件:

    function [value]=MFKnapsack(i,j)
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %输入:
    %       i:     --背包承受最大物品数
    %       j:     --背包承受最大重量
    %输出:
    %       value:  --最大价值
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    W=[2,1,3,2];%物品重量序列
    V=[12,10,20,15];%物品价值序列
    k=size(W,2);
    F=-ones(k,j);
    if(i~=0&&j~=0)
        if(F(i,j)<0)
            if(j
    function [s]=FindBag(i,j)
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %输入:
    %       i:     --背包承受最大物品数
    %       j:     --背包承受最大重量
    %输出:
    %       s:  
    %           s(1,1)      --最大价值
    %           s(1,2:end)  --背包内包含的物品
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    r=zeros(i,j);
    W=[2,1,3,2];%物品重量序列
    V=[12,10,20,15];%物品价值序列
    for p=1:1:i
        for q=1:1:j
            r(p,q)=MFKnapsack(p,q);
        end
    end
    k=i;
    l=j;
    s=[];
    sum=0;
    while(k>1)
        if(r(k,l)==r(k-1,l))
            k=k-1;
        else
            s=[s,k];
            sum=sum+V(1,k);
            l=l-W(1,k);
            k=k-1;
        end 
    end
    if(sum~=r(i,j))
        s=[s,1];
    end
    s=[r(i,j),s];
    end

     

     

     参考:(美)Anany Levitin 著 潘彦 译《算法设计与分析基础(第二版)》.清华大学出版社.北京.pag228-231

    展开全文
  • 彻底理解0-1背包问题

    万次阅读 多人点赞 2018-10-07 08:33:04
    0-1背包问题 给定n个重量为w1,w2,w3,…,wn,价值为v1,v2,v3,…,vn的物品和容量为C的背包,求这个物品中一个最有价值的子集,使得在满足背包的容量的前提下,包内的总价值最大 0-1背包问题指的是每个物品只能使用一...

    0-1背包问题

    给定n个重量为w1w_1w2w_2,w3w_3,…,wnw_n,价值为v1v_1,v2v_2,v3v_3,…,vnv_n的物品和容量为CC的背包,求这个物品中一个最有价值的子集,使得在满足背包的容量的前提下,包内的总价值最大

    0-1背包问题指的是每个物品只能使用一次

    递归方法

    首先我们用递归的方式来尝试解决这个问题
    我们用F(n,C)F(n,C)表示将前nn个物品放进容量为CC的背包里,得到的最大的价值。
    我们用自顶向下的角度来看,假如我们已经进行到了最后一步(即求解将nn个物品放到背包里获得的最大价值),此时我们便有两种选择

    1. 不放第nn个物品,此时总价值为F(n1,C)F(n-1,C)
    2. 放置第nn个物品,此时总价值为vn+F(n1,Cwn)v_n+F(n-1,C-w_n)

    两种选择中总价值最大的方案就是我们的最终方案,递推式(有时也称之为状态转移方程)如下
    F(i,C)=max(F(i1,C),v(i)+F(i1,Cw(i)))F(i,C)=max(F(i-1,C),v(i)+F(i-1,C-w(i)))
    编程实现如下:

    public class KnapSack01 {
        /**
         * 解决背包问题的递归函数
         *
         * @param w        物品的重量数组
         * @param v        物品的价值数组
         * @param index    当前待选择的物品索引
         * @param capacity 当前背包有效容量
         * @return 最大价值
         */
        private static int solveKS(int[] w, int[] v, int index, int capacity) {
            //基准条件:如果索引无效或者容量不足,直接返回当前价值0
            if (index < 0 || capacity <= 0)
                return 0;
    
            //不放第index个物品所得价值
            int res = solveKS(w, v, index - 1, capacity);
            //放第index个物品所得价值(前提是:第index个物品可以放得下)
            if (w[index] <= capacity) {
                res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
            }
            return res;
        }
    
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            return solveKS(w, v, size - 1, C);
        }
    
        public static void main(String[] args){
            int[] w = {2,1,3,2};
            int[] v = {12,10,20,15};
            System.out.println(knapSack(w,v,5));
        }
    }
    
    

    记忆化搜索

    我们用递归方法可以很简单的实现以上代码,但是有个严重的问题就是,直接采用自顶向下的递归算法会导致要不止一次的解决公共子问题,因此效率是相当低下的。
    我们可以将已经求得的子问题的结果保存下来,这样对子问题只会求解一次,这便是记忆化搜索。
    下面在上述代码的基础上加上记忆化搜索

    public class KnapSack01 {
        private static int[][] memo;
    
        /**
         * 解决背包问题的递归函数
         *
         * @param w        物品的重量数组
         * @param v        物品的价值数组
         * @param index    当前待选择的物品索引
         * @param capacity 当前背包有效容量
         * @return 最大价值
         */
        private static int solveKS(int[] w, int[] v, int index, int capacity) {
            //基准条件:如果索引无效或者容量不足,直接返回当前价值0
            if (index < 0 || capacity <= 0)
                return 0;
    
            //如果此子问题已经求解过,则直接返回上次求解的结果
            if (memo[index][capacity] != 0) {
                return memo[index][capacity];
            }
    
            //不放第index个物品所得价值
            int res = solveKS(w, v, index - 1, capacity);
            //放第index个物品所得价值(前提是:第index个物品可以放得下)
            if (w[index] <= capacity) {
                res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
            }
            //添加子问题的解,便于下次直接使用
            memo[index][capacity] = res;
            return res;
        }
    
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            memo = new int[size][C + 1];
            return solveKS(w, v, size - 1, C);
        }
    
        public static void main(String[] args) {
            int[] w = {2, 1, 3, 2};
            int[] v = {12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }
    
    

    动态规划算法

    在这里插入图片描述
    在这里插入图片描述

    public class KnapSack01 {
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            if (size == 0) {
                return 0;
            }
    
            int[][] dp = new int[size][C + 1];
            //初始化第一行
            //仅考虑容量为C的背包放第0个物品的情况
            for (int i = 0; i <= C; i++) {
                dp[0][i] = w[0] <= i ? v[0] : 0;
            }
    		//填充其他行和列
            for (int i = 1; i < size; i++) {
                for (int j = 0; j <= C; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (w[i] <= j) {
                        dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
                    }
                }
            }
            return dp[size - 1][C];
        }
    
        public static void main(String[] args) {
            int[] w = {2, 1, 3, 2};
            int[] v = {12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }
    
    

    空间复杂度的极致优化

    上面的动态规划算法使用了O(n*C)的空间复杂度(因为我们使用了二维数组来记录子问题的解),其实我们完全可以只使用一维数组来存放结果,但同时我们需要注意的是,为了防止计算结果被覆盖,我们必须从后向前分别进行计算
    在这里插入图片描述
    我们仍然假设背包空间为5,根据F(i,C)=max(F(i1,C),v(i)+F(i1,Cw(i)))F(i,C)=max(F(i-1,C),v(i)+F(i-1,C-w(i)))我们可以知道,当我们利用一维数组进行记忆化的时候,我们只需要使用到当前位置的值和该位置之前的值,举个例子
    假设我们要计算F(i,4)F(i,4),我们需要用到的值为F(i1,4)F(i-1,4)F(i1,4w(i))F(i-1,4-w(i)),因此为了防止结果被覆盖,我们需要从后向前依次计算结果
    最终的动态规划代码如下

    public class KnapSack01 {
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            if (size == 0) {
                return 0;
            }
    
            int[] dp = new int[C + 1];
            //初始化第一行
            //仅考虑容量为C的背包放第0个物品的情况
            for (int i = 0; i <= C; i++) {
                dp[i] = w[0] <= i ? v[0] : 0;
            }
    
            for (int i = 1; i < size; i++) {
                for (int j = C; j >= w[i]; j--) {
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
                }
            }
            return dp[C];
        }
    
        public static void main(String[] args) {
            int[] w = {2, 1, 3, 2};
            int[] v = {12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }
    
    

    利用背包问题的思想解决问题

    leetcode 416 Partition Equal Subset Sum

    给定一个仅包含正整数的非空数组,确定该数组是否可以分成两部分,要求两部分的和相等

    问题分析

    该问题我们可以利用背包问题的思想进行求解。

    假设给定元素个数为nn的数组arr,数组元素的和为sum,对应于背包问题,等价于有nn个物品,每个物品的重量和价值均为为arr[i],背包的限重为sum/2,求解背包中的物品最大价值为多少?

    class Solution {
        private boolean knapSack(int[] nums,int sum){
            int size = nums.length;
            
            boolean[] dp = new boolean[sum + 1];
            for (int i = 0;i <= sum;i ++){
               dp[i] = i == nums[0];
            }
            
            for (int i = 1;i < size;i++){
                for (int j = sum;j >= nums[i];j--){
                    dp[j] = dp[j] || dp[j-nums[i]];
                }
            }
            return dp[sum];
        }
        
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int item : nums){
                sum += item;
            }
            
            //如果数组元素和不是2的倍数,直接返回false
            if (sum % 2 != 0)
                return false;
            
            return knapSack(nums,sum/2);
        }
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,871
精华内容 12,748
关键字:

背包问题