带权活动安排（动态规划）

package org .sunny.dynamicProgram;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 有若干个活动，第i个活动的开始时间和终止时间分别为si和fi，活动之间不能交叠，
 * 举办一个活动可以得到的收益为wi，求最多能得到的最大收益。
 * 输入样例：第一行：活动的数目；之后每一行输入：活动其实时间 终止时间 收益
 4
 3 12 12
 9 11 4
 11 13 2
 13 15 1
 */
public class ActivityDecompose {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[][] timeTable = new int[num+1][3];

        for (int i=1;i<=num;i++){
            timeTable[i][0] = scanner.nextInt();  //start
            timeTable[i][1] = scanner.nextInt();  //end
            timeTable[i][2] = scanner.nextInt();
        }

        /*
        按照结束时间fi排序，dp[i]表示最后一个任务安排任务i时的最大收益，则有
        dp[i]=max(dp[j]+wi),j<i,fj<=si(任务j的终止时间小于任务i的开始时间)
         */
        Arrays.sort(timeTable,(o1,o2)->o1[1]-o2[1]);
        for (int[] row:timeTable){
            System.out.print("start="+row[0]+"---end="+row[1]+"--benifit="+row[2]);
            System.out.println();
        }

        /*
        dp[i]=max{dp[j]+wi},j<i,fj<=si
         */
        int[] dp = new int[num+1];
        for (int i=1;i<=num;i++){
            int maxValue = timeTable[i][2];  //初始化最大收益
            for (int j=1;j<i;j++){
                if (timeTable[i][0]>=timeTable[j][1]){

                    maxValue = Math.max(maxValue,timeTable[i][2]+dp[j]);

                }
            }
            dp[i] = maxValue;
        }

        System.out.println(Arrays.toString(dp));
    }
}