题目

一份工作有开始时间和结束时间以及价值三个属性，在0时到11时一共有8份工作可以自有安排。一个人应该如何安排才能够收获最大工资？注意：只能同时干一份工作。

解题思路

首先对所有工作按照结束时间升序排列，求出假如选择第n份工作的情况，上一份工作的下标prev(n)，并填入数组。接下来就是使用动态规划解题，分别对选择第n份工作和不选第n份工作获取的价值进行对比，择出较大价值的填入opt数组。

代码实现

Java版

package com.nekoc.dp;

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();
        job[] jb= new job[count];
        //下边的for循环一定要写呀,不然就会抛出空指针异常呀,浪费好多时间.
        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 opt[] = new int[count];
        int pre[] = new int[count];
        pre[0]=0; //设置好prev0为0
        //找出所有prev,从数组第二项开始
        for(int i=1;i<count;i++) {
            for(int j=i-1;j>=0;j--) { //选中一项，往前对比
                if(jb[i].start>=jb[j].end) {
                    pre[i]=j+1;
                    break;
                }
            }
        }

        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;
               // opt[i]=opt【i-1】>job[i].price+opt【PRE[i】-1]?OPT【i-1】:JOB[i].price+OPT【PRE[i】-1];

            }
        }
        for(int i=0;i<count;i++) {
            System.out.println("第"+(i+1)+"个点的最优解是:"+opt[i]);
        }
    }
}

python版

import numpy as np


class Meeting:
    def __init__(self, begin, end, value):
        self.begin = begin
        self.end = end;
        self.value = value


meets = []
length_size = 8

# 加入数据
for i in range(length_size):
    begin = input("begin")
    end = input("end")
    value = input("value")
    m = Meeting(begin, end, value)
    meets.append(m)

prev = np.zeros(length_size)
opt = np.zeros(length_size)
opt[0] = int(meets[0].value)
prev[0] = 0

# 填好prev
for i in range(1, length_size):
    for j in range(i - 1, -1, -1):
        if int(meets[i].begin) >= int(meets[j].end) :
            print("满足条件的是i=" + str(i) + ",j=" + str(j))
            print(str(meets[i].begin))
            print(meets[j].end)
            prev[i] = j + 1
            break

# 输出prev
for i in prev:
    print(str(i) + "  ")

for i in range(1, length_size):
    if (prev[i] == 0):
        # 假设是第二项 有选和不选
        opt[i] = max(int(meets[i].value), int(opt[i - 1]))
    else:
        # 这里分 选 和 不选
        A = int(opt[int(prev[i-1])]) + int(meets[i].value)
        B = int(opt[i - 1])
        opt[i] = max(A, B)

# 输出一下结果数组
for i in range(len(opt)):
    print("第" + str((i + 1)) + "个点的最优解是:" + str(opt[i]));

别问为什么没有C语言版，因为我辣鸡！！！同样的思路到C语言那边就出现很奇怪的问题。

运行截图

输入例子 开始时间 结束时间 价值
(1 4 5) (3 5 1) (0 6 8) (4 7 4) (3 8 6) (5 9 3) (6 10 2) (8 11 4)

版权属于：本文为原创文章，版权归 猫先生 所有

本文链接：https://loli.rip/index.php/archives/223/

转载时须注明出处及本声明