2.07 算法练习

1. 多重背包基础问题

算法思路

1. 每个物品有限制数量，相当于多个数量的0-1背包问题；
2. 可以把每种商品遍历的个数放在0-1背包里面在遍历一遍。

注意点

1. 遍历条件需要变为 j>=k*weight[i]，以及递归公式变为dp[j-k * weight[i]] + k * value[i]；
2. 因为变为了多个数量的0-1背包问题，所以倒序遍历背包。

代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int bagweight = sc.nextInt();
        int n = sc.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        int[] nums = new int[n];
        
        for(int i = 0; i<n; i++) weight[i] = sc.nextInt();
        for(int i = 0; i<n; i++) value[i] = sc.nextInt();
        for(int i = 0; i<n; i++) nums[i] = sc.nextInt();
        
        // 装满容量为j的背包的最大价值为dp[j]
        int[] dp = new int[bagweight+1];
        dp[0] = 0;
        
        for(int i = 0; i<n; i++){
            for(int j = bagweight; j >= weight[i]; j--){
                // 遍历每个物品的个数
                for(int k = 0; k<=nums[i] && j>=k*weight[i]; k++){
                    dp[j] = Math.max(dp[j], dp[j-k * weight[i]] + k * value[i]);
                    
                }
            }
        }
        
        System.out.println(dp[bagweight]);
        
    }
}