背包问题——（0-1背包）

/**
 * FileName: Main
 * Author:   Jerry
 * Date:     2020/1/27 18:59
 * Description: 背包问题（0-1）
 * 问题描述：
 * 一个背包的总容量为V,现在有N类物品,第i类物品的重量为weight[i],价值为value[i]
 * 那么往该背包里装东西,怎样装才能使得最终包内物品的总价值最大。这里装物品主要由三种装法：
 * 1、0-1背包：每类物品最多只能装一次
 * 2、多重背包：每类物品都有个数限制，第i类物品最多可以装num[i]次
 * 3、完全背包：每类物品可以无限次装进包内
 */
package com.ljl;
 
public class Main {
    /*0-1背包问题
    * @ V 背包容积
    * @ N 物品种类
    * @ weight 物品重量
    * @ value 物品价值
    * */
 
    public static void zeroOnePack(int V,int N,int []weight,int []value)
    {
        int [][]dp = new int[N+1][V+1];
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=V;j++)
            {
                if(weight[i]>j)
                    dp[i][j]=dp[i-1][j];
                else
                {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }
        //则容量为V的背包能够装入物品的最大值为
        int maxValue = dp[N][V];
        int j=V;
        String numStr="";
        System.out.println("最大价值为"+dp[N][V]);
        for(int i=N;i>=1;i--)
        {
            if(dp[i][j]>dp[i-1][j])
            {
                numStr += i+" ";
                j=j-weight[i];
            }
            if(j==0)
                break;
        }
        System.out.println("所选货物标签为"+numStr);
    }
    public static void main(String []args)
    {
        int [] w = new int[]{0,2,3,4,5};
        int [] v = new int[]{0,3,4,5,6};
        int bagV =8;
        zeroOnePack(bagV,4,w,v);
    }
 
}

1、0-1背包实现原理及代码

更多原理部分参考： https://blog.csdn.net/xp731574722/article/details/70766804

a)求解背包所含物品的最大值：

利用动态规划求最优值的方法。假设用dp[N][V]来存储中间状态值,dp[i][j]表示前i件物品能装入容量为j的背包中的物品价值总和的最大值(注意是最大值),则我们最终只需求知dp[i=N][j=V]的值，即为题目所求。

现在考虑动态规划数组dp[i][j]的状态转移方程：

假设我们已经求出前i-1件物品装入容量j的背包的价值总和最大值为dp[i-1][j],固定容量j的值不变，则对第i件物品的装法讨论如下：

首先第i件物品的重量weight[i]必须小于等于容量j才行，即

1、若weight[i]>j,则第i件物品肯定不能装入容量为j的背包，此时dp[i][j]=dp[i-1][j]

2、若weight[i]<=j,则首先明确的是这件物品是可以装入容量为j的背包的，那么如果我们将该物品装入，则有

dp[i][j]=dp[i-1][j-weight[i]]+value[i]

随之而来的问题是我们要判断第i件物品装到容量为j的背包后,背包内的总价值是否是最大？其实很好判断，即如果装了第i件物品后的总价值dp[i-1][j-weight[i]]+value[i]>没装之前的总价值最大值dp[i-1][j]，则肯是最大的；反之则说明第i件物品不必装入容量为j的背包(装了之后总价值反而变小，那么肯定就不需要装嘛)

故，状态转移方程如下：

dp[i][j] = (dp[i-1][j] > (dp[i-1][j-weight[i]]+value[i]))? dp[i-1][j]:(dp[i-1][j-weight[i]]+value[i])

注意：这里的前i件物品是给定次序的

b)求出背包中装入物品的编号

这里我们采用逆推的思路来处理，如果对于dp[i][j]>dp[i-1][j]，则说明第i个物品肯定被放入了背包，此时我们再考察dp[i-1][j-weight[i]]的编号就可以了。