DP-求最大值求最优解

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

### Description ###

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

### Solution ###

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

**2.求出前置任务**  
![在这里插入图片描述][20181122215013780.png]  
3.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzYyNjc3_size_16_color_FFFFFF_t_70 1]

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]);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzYyNjc3_size_16_color_FFFFFF_t_70]: /images/20220415/c6abd1a60d484f08855273bd4bf6e440.png
[20181122214332291.png]: /images/20220415/3f33f3dd34574f87a168b060f5e2adbf.png
[20181122215013780.png]: /images/20220415/1384da58750e41739cd8e0738678dd5f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzYyNjc3_size_16_color_FFFFFF_t_70 1]: /images/20220415/031ca0c07c984556bb7ec687c5bca7f1.png