LeetCode刷题笔记之动态规划（二）

一、0-1背包问题

有一个限制容量的背包，有n个具有不同价值v和重量w的物体，求放入这个背包的最大价值。（一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包）

• 二维形式：
  （1）首先找状态，【限制容量的背包】【有价值和重量的物体】，因此确定dp数组是二维的
  （2）dp[i][j]表示容量为j的背包，选择第i个物体时的最大价值
  （3）dp[i][j] = max(dp[i-1][j]，dp[i-1][j-w[i]]+v[i]) //如果背包里放不下，则与上下两个值相同；如果可以放下，则是上一行的某个值加上第i个物品的价值。
  （4）dp[][0]=0，dp[0][j>=w[i]]=v[i]
• 一维形式：
  （1）每一列只保留最大值，也就是说总共n行压缩为1行，这一行的值均为2维时数组的最大值
  （2）dp[j]=max(dp[j]，dp[j-w[i]]+v[i])
  （3）dp[0]=0

1. 卡码网46 【携带研究材料（第六期模拟笔试）】

• 题目： 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
  小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

• 输入描述： 输入描述

  • 第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
  • 第二行包含 M 个正整数，代表每种研究材料的所占空间。
  • 第三行包含 M 个正整数，代表每种研究材料的价值。

• 输出描述： 输出一个整数，代表小明能够携带的研究材料的最大价值。

• 代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int M = scan.nextInt();
        int N = scan.nextInt();
        int[] space = new int[M];
        int[] value = new int[M];
        int[][] dp = new int[M][N+1];
        for(int i=0;i<M;i++){
            space[i] = scan.nextInt();
            dp[i][0] = 0;
        }
        for(int i=0;i<M;i++){
            value[i] = scan.nextInt();
        }
        for(int i=space[0];i<=N;i++){
            dp[0][i] = value[0];
        }
        for(int i=1;i<M;i++){
            for(int j=1;j<=N;j++){
                if(j>=space[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-space[i]]+value[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
                
            }
        }
        System.out.println(dp[M-1][N]);
    }
}

2. 416【分割等和子集】

• 题目： 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
• 代码：

class Solution {
    public boolean canPartition(int[] nums) {
        //将题目转换成01背包问题，数组为背包，背包的容量为sum/2，
        //物品是数组中的元素，w和v均为元素的值
        //dp表示背包容量为i时的最大价值
        //dp[i] = max(dp[i],dp[i-w[j]]+v[j])
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        //如果sum为奇数则不能平分
        if(sum%2 == 1) return false;
        int[] dp = new int[sum/2+1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            //从最大值开始遍历，直到j<nums[i]
            for (int j = sum/2; j>=nums[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
            if(dp[sum/2] == sum/2)
                return true;
        }
        return dp[sum/2] == sum/2;
    }
}

3. 1049【最后一块石头的重量II】

• 题目： 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
    最后，最多只会剩下一块石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
• 代码：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        //可以考虑将这些石头尽量平均分为两组，用总和-2*min(group1,group2)，就是最后能够剩下的最小重量
        //dp表示当剩余重量为j时，还可以放下的最大价值
        //dp[j] = max(dp[j],dp[j-s[i]]+s[i])
        //dp[0] = 0
        int sum = 0;
        for(int i=0;i<stones.length;i++){
            sum += stones[i];
        }
        int[] dp = new int[sum/2+1];
        dp[0] = 0;
        for (int i = 0; i < stones.length; i++) {
            for (int j=sum/2; j>=stones[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[sum/2];
    }
}