洛谷AC：采药问题 - 动态规划

题目链接

P1048 [NOIP2005 普及组] 采药

题目描述

实现代码

思路：每一个草药都有两种选择：采或者不采，因此可以通过DFS的形式对这两种选择进行比较去最优解；

采用DFS的形式实现：

import java.util.Scanner;
/**
 * @Description:
 * @Author: JreamY
 * @Date: 2022/2/25
 **/
public class Demo {
    static int result = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();  // 总采药时间
        int M = in.nextInt();  // 草药总数
        int[] times = new int[M + 1];
        int[] values = new int[M + 1];
        for (int i = 1; i <= M; i++) {
            times[i] = in.nextInt();
            values[i] = in.nextInt();
        }
        in.close();
        dfs(1, T, M, times, values, 0);
        System.out.println(result);
    }
    public static void dfs(int pos, int T, int M, int[] times, int[] values, int res) {
        if (pos == M + 1) {
            result = (result > res ? result : res);
            return;
        }
        if (T < 0) {
            return;
        }
        // pos位置的药采
        dfs(pos + 1, T, M, times, values, res);
        // pos位置的药不采
        dfs(pos + 1, T - times[pos], M, times, values, res + values[pos]);
    }
}

进一步简化dfs，使其变成有返回的方法：

package ccnu.agile.jdk8;
import java.util.Scanner;
/**
 * @Description:
 * @Author: JreamY
 * @Date: 2022/2/25
 **/
public class Demo {
    static int result = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();  // 总采药时间
        int M = in.nextInt();  // 草药总数
        int[] times = new int[M + 1];
        int[] values = new int[M + 1];
        for (int i = 1; i <= M; i++) {
            times[i] = in.nextInt();
            values[i] = in.nextInt();
        }
        in.close();
        System.out.println(dfs2(1, T, M, times, values));
    }
    public static int dfs2(int pos, int T, int M, int[] times, int[] values) {
        if (pos == M + 1) {
            return 0;
        }
        int unUseResult, useResult = Integer.MIN_VALUE;
        unUseResult = dfs2(pos + 1, T, M, times, values);
        if (T >= times[pos]) {
            useResult = dfs2(pos + 1, T - times[pos], M, times, values) + values[pos];
        }
        return Math.max(useResult, unUseResult);
    }
}

在dfs递归过程中做了很多重复的dfs操作，因此可以通过标记将已经做过操作的保存起来，查询条件为：pos + T：

package ccnu.agile.jdk8;
import java.util.Scanner;
/**
 * @Description:
 * @Author: JreamY
 * @Date: 2022/2/25
 **/
public class Demo {
    static int result = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();  // 总采药时间
        int M = in.nextInt();  // 草药总数
        int[] times = new int[M + 1];
        int[] values = new int[M + 1];
        for (int i = 1; i <= M; i++) {
            times[i] = in.nextInt();
            values[i] = in.nextInt();
        }
        in.close();
        int[][] mem = new int[M+2][T+1];
        for(int i=1; i<=M+1; i++) {
            for(int j=1; j<=T; j++) {
                mem[i][j] = -1;
            }
        }
        System.out.println(dfs3(1, T, M, times, values, mem));
    }
    public static int dfs3(int pos, int T, int M, int[] times, int[] values, int[][] mem) {
        if(mem[pos][T] != -1) {
            return mem[pos][T];
        }
        if (pos == M + 1) {
            return mem[pos][T] = 0;
        }
        int unUseResult, useResult = Integer.MIN_VALUE;
        unUseResult = dfs3(pos + 1, T, M, times, values, mem);
        if (T >= times[pos]) {
            useResult = dfs3(pos + 1, T - times[pos], M, times, values, mem) + values[pos];
        }
        return mem[pos][T] = Math.max(useResult, unUseResult);
    }
}

进一步的来看，可以发现，每一步的结果可以通过已经得到的结果进行表示，即DP，对应的状态转移方程为：

mem[pos][T] = max(mem[pos+1][T], mem[pos+1][T-times[pos]] + values[pos]);