寒假每日一题打卡day23——AcWing 426. 开心的金明

【题目描述】

动态规划

【思路】 01背包，二维数组f[i][j], 第一维度表示物品，第二维度表示钱数，f[i][j]表示前i种物品中价格不超过j的最大目标值。

import java.io.*;
import java.lang.Math;
class Main{
          
   
    static int N = 30010 , M = 30;
    public static void main(String args[])throws Exception{
          
   
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        String s[] = bf.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int v[] = new int[M];
        int p[] = new int[M];
        //物品  钱数
        //f[i][j]表示前i种物品 总钱数不超过j的最大目标值（总钱数的物品的价格与重要度乘积的总和）
        for(int i = 1; i <= m; i++){
          
   
            String data[] = bf.readLine().split(" ");
            v[i] = Integer.parseInt(data[0]);
            p[i] = Integer.parseInt(data[1]);
        }
        int f[][] = new int[M][N];
        for(int i = 1; i <= m; i++ ){
          
   
            for(int j = 1; j <= n; j++){
          
   
                if( j >= v[i] )
                //选（f[i - 1][j - v[i] + v[i]*p[i]）+与不选（f[i - 1][j]）的较大者
                f[i][j] = Math.max(f[i - 1][j - v[i]] + v[i]*p[i], f[i - 1][j]);
                else f[i][j] = f[i - 1][j];
            }
        }
        log.write(f[m][n]+"
");
        log.flush();//要从缓冲区flush出去才会打印
        log.close();
        bf.close();
        
    }
}