开心的金明-题解（自定义类+动态规划Java代码）

解题思路:经典的01背包解法，比较简单

注意事项:这里使用了逆序的一维dp数组来存放价值结果，需要小心的是dp的大小是比钱的数量多一位的，比较方便观察，要注意将01背包问题中的value改为value*重要程度。这里创建购买物品的类时没有把重要程度作为对象属性输入，个人认为这样比较简洁。

参考代码:

import java.util.Scanner;
import java.util.ArrayList;
public class Main {

    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	String[] input = scan.nextLine().split(" ");
    	int Money = Integer.parseInt(input[0]);
    	int Number = Integer.parseInt(input[1]);
    	ArrayList<buy> a = new ArrayList<buy>();
    	for (int i = 0; i < Number; i++) {
    		input = scan.nextLine().split(" ");
    		a.add(new buy(Integer.parseInt(input[0]),Integer.parseInt(input[1])));
    	}
    	scan.close();
    	System.out.println(shop(Money,Number,a));
    	
    }//main
    public static int shop(int m,int n,ArrayList<buy> a) {
    	int[] dp = new int[m+1];
    	for (int i = 1; i < n+1; i++) {
    		for (int j = m; j > a.get(i-1).money; j--) {
    			dp[j] = Math.max(dp[j], dp[j-a.get(i-1).money] + a.get(i-1).value);		
    		}
    	}
    	return dp[m];
    }
}//Class Main
	class buy {
		int money;
		int value;
		buy(int a,int b){
			this.money = a;
			this.value = a * b;
		}
	}