Day46代码随想录(1刷) 多重背包+动态规划

多重背包

多重背包就是物品数量不是只有一个也不是无限取而是有一个有限数量，我们可以把数量大过1的物品铺开也就是0-1背包问题了，所以多重背包可以转换成0-1背包

56. 携带矿石资源（第八期模拟笔试）

题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。 

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。 

接下来的三行，每行包含 N 个正整数。具体如下： 

第二行包含 N 个整数，表示 N 种矿石的重量。 

第三行包含 N 个整数，表示 N 种矿石的价格。 

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出描述

输出一个整数，代表获取的最大价值。

输入示例

10 3
1 3 4
15 20 30
2 3 2

输出示例

90

提示信息

数据范围：
1 <= C <= 10000;
1 <= N <= 10000;
1 <= w[i], v[i], k[i] <= 10000;

状态：完成

思路：除了遍历物品和背包容量还要在里层把物品铺开就是要遍历物品数量转换成0-1背包，状态转移方程是：

import java.util.*;
class Main{
    public static void main (String[] args) {
        /* code */
        Scanner sc=new Scanner(System.in);
        int C=sc.nextInt();
        int N=sc.nextInt();
        int[] weights=new int[N];
        int[] values=new int[N];
        int[] nums=new int[N];
        int[] dp=new int[C+1];
        for(int i=0;i<N;i++) weights[i]=sc.nextInt();
        for(int i=0;i<N;i++) values[i]=sc.nextInt();
        for(int i=0;i<N;i++) nums[i]=sc.nextInt();
        for(int i=0;i<N;i++){
            for(int j=C;j>=0;j--){
                
                for(int k=1;k<=nums[i];k++){
                    if(j-k*weights[i]<0) continue;
                    dp[j]=Math.max(dp[j],dp[j-k*weights[i]]+k*values[i]);
                }
                
            }
        }
        System.out.println(dp[C]);
        
    }
}

 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

状态：完成

思路：这题比较简单，dp[i]表示这个房子时能偷走的最大价值，因为偷这个房子选不选取决于前一个房子和前两个房子，偷了上一家这家就不能偷，所以动态转移方程为：

                ​​​​​​​        

class Solution {
    public int rob(int[] nums) {
        int[] dp=new int[nums.length];
        if(nums.length==1) return nums[0];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }
}

 213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

状态：自己没写出来看一下思路就写出来了。

思路：这题有环路所以判断就会变得麻烦所以我们可以拆成两个非环路进行比大小，对nums[0]进行讨论是否取，如果取则只能从[2,n-1)中讨论偷不偷，如果不取从[1,n)中讨论，所以最后只要比较两个环路的大小就ok了。

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        return Math.max(rob1(Arrays.copyOfRange(nums,1,n)),nums[0]+rob1(Arrays.copyOfRange(nums,2,n-1)));
    }
    public int rob1(int[] nums) {
        if(nums.length==0) return 0;
        int[] dp=new int[nums.length];
        if(nums.length==1) return nums[0];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }
}