[数据结构与算法]多重背包的二进制优化

多重背包的二进制优化

多重背包

• 比较朴素的多重背包（空间使用了一维数组优化）

public int multiBag( int[] weight , int[] value , int[] num , int capacity )
{
    int[] dp = new int[capacity+1];
    int len = weight.length;

    //第一层 枚举前 i 个物品是否可用
    for( int i=1 ; i<=len ; i++ )
        //第二层 枚举背包容量
        for( int j=capacity ; j>=0 ; j-- )
            //第三层 枚举物品数量 (这里的 `k<=num[i-1]` 就是多重背包问题与完全背包问题的区别)
            for( int k=0 ; k<=num[i-1] && k*weight[i-1]<=j ; k++ )
                dp[j] = Math.max( dp[j] , dp[j-k*weight[i-1]]+k*value[i-1] );

    return dp[capacity];
}

很显然，上述算法主体部分有三层循环，时间复杂度为 n^3（大概）

扁平化处理

事实上，多重背包问题是可以转换成0-1背包问题的我们可以通过 扁平化 来转换

比如，数量为 10 的物品 b 可以转换成 10 个物品 b

[b] [10] --> [bbbbbbbbbb] （也就是把 sum 数组展开到 weight 和 value 数组中）

public int multiBag( int[] weight , int[] value , int[] num , int capacity )
{
    ArrayList<Integer> nweight = new ArrayList<>();
    ArrayList<Integer> nvalue = new ArrayList<>();
    //首先预处理 将 num 数组展开
    for( int i=0 ; i<weight.length ; i++ )
    {
        for( int j=0 ; j<num[i] ; j++ )
        {
            nweight.add( weight[i] );
            nvalue.add( value[i] );
        }
    }

    //之后对 nweight nvalue 进行 0-1 背包问题求解即可
    int[] dp = new int[capacity+1];
    int len = nweight.size();

    //第一层 枚举前 i 个物品是否可用
    for( int i=1 ; i<=len ; i++ )
        //第二层 枚举背包容量
        for( int j=capacity ; j>=0 ; j-- )
            if( j-nvalue.get(i-1)>=0 )
                dp[j] = Math.max( dp[j] , dp[j-nweight.get(i-1)]+nvalue.get(i-1) );

    return dp[capacity];
}

很显然，上述算法并没有减少时间复杂度（相反还增加了常数级别的复杂度）

二进制优化

• 引子

我们使用 1 2 4 的 0-1 选择可以实现 0~7的组合

? [] [1] [2] [1 2] [4] [1 4] [2 4] [1 2 4]

同样的道理 我们在扁平化一个数量为7的物品时，可以将其展开为三个物品

? [b] [7] --> [ b 2b 4b ]

这样就可以有效的降低复杂度

要注意的是，我们要保证组合最大值不能超过物品数量

比如

? [b] [10] --> [ b 2b 4b 3b ]

(3=10-7)

同理 如果是 数量为 25 的物品，我们可以展开为

1 2 4 8 10

（既保证了 0-1 选择可以完全覆盖 0~25 又保证了不会出现选择的物品数量大于 25 的情况）

public int multiBag( int[] weight , int[] value , int[] num , int capacity )
{
    ArrayList<Integer> nweight = new ArrayList<>();
    ArrayList<Integer> nvalue = new ArrayList<>();
    //首先预处理 将 num 数组展开(二进制优化)
    for( int i=0 ; i<weight.length ; i++ )
    {
        int n = num[i];
        for( int j=1 ; j<=n ; j*=2 )
        {
            n-=j;
            nweight.add( weight[i]*j );
            nvalue.add( value[i]*j );
        }
        if( n>=0 )
        {
            nweight.add( weight[i]*n );
            nvalue.add( value[i]*n );
        }
    }
    //之后对 nweight nvalue 进行 0-1 背包问题求解即可
    int[] dp = new int[capacity+1];
    int len = nweight.size();

    //第一层 枚举前 i 个物品是否可用
    for( int i=1 ; i<=len ; i++ )
        //第二层 枚举背包容量
        for( int j=capacity ; j>=0 ; j-- )
            if( j-nvalue.get(i-1)>=0 )
                dp[j] = Math.max( dp[j] , dp[j-nweight.get(i-1)]+nvalue.get(i-1) );

    return dp[capacity];
}