背包问题之多重背包

package com.zhang.reflection.面试.算法模版.背包问题模版;

/**
 * 有N种物品和一个容量为V的背包。第i种物品最多有p[i]件可用，每件费用是w[i]，价值是v[i]。
 * 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
 */

public class 多重背包 {
    public static void main(String[] args) {
        //物品个数
        int numbers = 4;
        //背包容量
        int capacity = 5;
        //个体容量
        int[] weight = {1, 2, 3, 4};
        //个体价值
        int[] values = {2, 4, 4,5};
        //第i种物品最多有p[i]件可用
        int[] p = {3, 1, 3, 2};
        //当前背包容量 j的物品最佳组合对应的价值
        int[] v = new int[capacity + 1];
        //这是未优化的版本：根据01背包思路，但是可能会超时
//        for(int i=0;i<numbers;i++){
//            for(int j=capacity;j>=weight[i];j--){
//                for(int k=0;k<=p[i]&&j>=k*weight[i];k++){
//                    v[j]=Math.max(v[j],v[j-k*weight[i]]+k*values[i]);
//                }
//            }
//        }

//        这是优化之后的版本(回头看看背包九讲...)：
        for (int i = 0; i < numbers ; i++) {
            //每次增长一倍，减少计算量
            int num = Math.min(p[i], capacity / weight[i]);
            for (int k = 1; num > 0; k <<= 1) {
                if (k > num) {
                    k = num;
                }
                num = num - k;
                for (int j = capacity; j >= weight[i] * k; j--) {
                    v[j] = Math.max(v[j], v[j - weight[i] * k] + values[i] * k);
                }
            }
        }
        System.out.println(v[capacity]);
    }
}