开心的金明 (java版)

解题思路:

    经典的01背包问题  使用动态规划 dp dfs都可

注意事项:

参考代码:

import java.util.Scanner;

public class Main {

    //最大总和, 物品数目
    static int MAX, m;
    static int[][] numArr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N =  sc.nextInt();
        m = sc.nextInt();
        numArr = new int[m][2];
        for (int i = 0; i < m; i++) {
            int money = sc.nextInt();
            int count = sc.nextInt();
            if (money < N) {
                numArr[i][0] = count;
                numArr[i][1] = money;
            }
        }
        dfs(N, 0, 0);
        System.out.println(MAX);
    }
    static void dfs(int N, int sum, int i) {
        if (sum > MAX) {
            MAX = sum;
        }
        for (i = i; i < m; i++) {
            if (N >= numArr[i][1]) {
                dfs(N - numArr[i][1], sum + numArr[i][0] * numArr[i][1], i + 1);
            }
        }
    }
}