import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MultiBagProblem {
    public static void main(String[] args) {
        // 物品信息
        /**
         *          重量  价值  数值
         *  物品0     1    15    2
         *  物品1     3    20    3
         *  物品2     4    20    2
         */
        List<Integer> weight = new ArrayList<>(Arrays.asList(1,3,4));
        List<Integer> value = new ArrayList<>(Arrays.asList(15,20,30));
        List<Integer> nums = new ArrayList<>(Arrays.asList(2,3,3));
        // 背包信息
        int bagSize = 10;
        multiBag(weight,value,nums,bagSize);
    }
    /**
     *
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param nums    物品的数量
     * @param bagSize 背包的容量
     */
    private static void multiBag(List<Integer> weight,
                          List<Integer> value,
                          List<Integer> nums,
                          int bagSize) {
        /**
         * 将物品展开
         */
        // 先把物品展开，展开成一个物品只有一个
        for (int i = 0; i < nums.size(); i++) {
            while (nums.get(i) > 1) {
                weight.add(weight.get(i));
                value.add(value.get(i));
                nums.set(i , nums.get(i) - 1);   // 展开一个，原数量就减一
            }
        }
        /**
         * 按照01背包进行装包
         */
        // 创建dp数组
        int[] dp = new int[bagSize+1];
        // 遍历更新dp数组
        for (int i = 0; i < weight.size(); i++) {  // 先对物品进行遍历
            for (int j = bagSize; j >= weight.get(i); j--) {  // 再对背包进行倒序遍历
                dp[j] = Math.max(dp[j],dp[j-weight.get(i)] + value.get(i));
            }
            // 打印dp数组
            System.out.println("物品" + i + "\t" + Arrays.toString(dp));
        }
    }
}