算法-动态规划-多重背包

Keep thinking. / 2024-09-02 / 原文

0. 动态规划五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

1. 多重背包问题

多重背包指的是每个物品最多可以选取num[i]次
将每个物品展开，多重背包问题就可以转化为01背包问题。

import java.util.Scanner;

public class Main{
    // 多重背包可以转化为01背包问题
    public static void  main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int bagWeight = scanner.nextInt();
        int n = scanner.nextInt();
        
        int[] weight = new int[n];
        int[] value = new int[n];
        int[] num = new int[n];
        for(int i = 0; i<n; ++i)    weight[i] = scanner.nextInt();
        for(int i = 0; i<n; ++i)    value[i] = scanner.nextInt();
        for(int i = 0; i<n; ++i)    num[i] = scanner.nextInt();
        
        int[] dp = new int[bagWeight+1];
        
        for(int i = 0; i<n; ++i) {
            // 对于每一种物品，循环k次
            for(int k = 1; k<=num[i]; ++k) {
                for(int j = bagWeight; j>=weight[i]; --j) {
                    dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
                }
            }
        }
        
        System.out.println(dp[bagWeight]);
    }
}