背包问题之混合背包

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

import java.util.Scanner;

/**题干一：
 * 如果将前三种混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），
 * 有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？
 *
 * 题干二：
 * 有 N 种物品和一个容量是 V 的背包。
 * 物品一共有三类：
 * 第一类物品只能用1次（01背包）；
 * 第二类物品可以用无限次（完全背包）；
 * 第三类物品最多只能用 si 次（多重背包）；
 * 每种体积是 vi，价值是 wi。
 * si=−1 表示第 i 种物品只能用1次；
 * si=0 表示第 i 种物品可以用无限次；
 * si>0 表示第 i 种物品可以使用 si 次；
 * 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
 */

public class 混合背包 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 物品个数
        int V = sc.nextInt(); // 背包总容量
        int[] dp = new int[V + 1];
        for(int i = 0; i < N; i++){
            int v = sc.nextInt(); // 体积
            int w = sc.nextInt(); // 价值
            int s = sc.nextInt(); // 数量
            if(s == 0){
                // 完全背包问题
                for(int j = v; j <= V; j++){
                    dp[j] = Math.max(dp[j], dp[j - v] + w);
                }
            }else{
                // 多重背包问题，01背包是多重背包的特例，可以一并处理
                //即要么为1个要么为多个
                s = Math.abs(s);
                int num=Math.min(s,V/v);
                for(int j = 1; num>0; j<<=1){
                    if(j>num){
                        j=num;
                    }
                    num=num-j;
                    for(int k = V; k >= j * v; k--){
                        dp[k] = Math.max(dp[k], dp[k - j * v] + j * w);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}