DP-求最大值求最优解-蒲公英云

DP-求最大值求最优解

悠悠 2022-04-15 07:08 315阅读 0赞

Description

分配了8个任务,时间不冲突的情况下,挣得工资最多
在这里插入图片描述

Solution

1.求OPT(i)
如果选了第i个,公式为第i个能挣得钱数加上上一个能选的OPT
Vi+OPT(prev(i))
如果没选第i个,公式就是求上一个能赚的最多的钱数
OPT(i-1)
解释
OPT(i)做第i个任务,能赚多少钱
prev(i)做第i个任务,上一个能做的任务的位置
在这里插入图片描述

2.求出前置任务
在这里插入图片描述

在这里插入图片描述

import java.util.Scanner;

class job { //任务类

int start;
int end;
int payment;

}

public class DPMaxSalary {

public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in);
    int count = sc.nextInt();
    //保存输入信息到jb对象数组
    job[] jb = new job[count];
    for (int i = 0; i < count; i++) { 
        jb[i] = new job();
    }
    for (int i = 0; i < count; i++) { 
        jb[i].start = sc.nextInt();
        jb[i].end = sc.nextInt();
        jb[i].payment = sc.nextInt();
    }
    //==========录入前置节点==================
    int pre[] = new int[count];
    pre[0] = 0;
    for (int i = 1; i < count; i++) { 
        for (int j = i - 1; j >= 0; j--) { 
            //一直没进if的自动初始化为0
            if (jb[i].start >= jb[j].end) { 
                pre[i] = j + 1;
                break;
            }
        }
    }
    //==========最优解==================
    int opt[] = new int[count];
    opt[0] = jb[0].payment;
    for (int i = 1; i < count; i++) { 
        if (pre[i] == 0) { 
            opt[i] = jb[i].payment > opt[i - 1] ? jb[i].payment : opt[i - 1];
        } else { 
            opt[i] = opt[i - 1] > opt[pre[i - 1]] + jb[i].payment ? opt[i - 1] : opt[pre[i - 1]] + jb[i].payment;
        }
    }
    for (int i = 0; i < count; i++) { 
        System.out.println("第" + (i + 1) + "个点的最优解是:" + opt[i]);
    }
}