算法<十>动态规划算法

package com.example.demo.SortAlgorithm;
import java.util.Scanner;
/*
 * @Author: i_heh
 * @Date: 2019/7/5
 * @Time: 14:28
 * @Description: 动态规划算法
 */
public class DynamicProgramming {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();//表示总钱数
        int m = scanner.nextInt();//表示希望购买的物品个数
        int a[][] = new int[m+1][2];//建立一个数组存放数据
        for(int i = 1;i<m+1;i++){
            a[i][0]=scanner.nextInt();//该件物品的钱数
            a[i][1]=scanner.nextInt();//该件物品的重要度
        }
        int pd[]= new int[N+2];//这就是动态规划的数组
        for(int i = 1 ;i<m+1;i++){//开始循环每一件商品，从第一件开始，请注意我这里的下标都是从1开始计算的（个人习惯）
            for(int j = N ;j>0;j--){
                if(j-a[i][0]>=0){
                    pd[j]=Math.max(pd[j],pd[j-a[i][0]]+a[i][1]*a[i][0] );
                }
                else {
                    pd[j]=pd[j];
                }
            }
        }
        int sum = 0;//这里存放我们的最终值，就是选中的商品的价格与其重要度的乘积之和
        for(int i = 1; i<=N;i++){
            sum = pd[i]>sum?pd[i]:sum;//判断动态规划数组中的最大数值
        }
        System.out.println(sum);
    }
}