可以做ps兼职的网站seo网址大全

【题目描述】

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]+"\n");log.flush();//要从缓冲区flush出去才会打印log.close();bf.close();}
}