题解 | #训练聪明的牛II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @param totalWeight int整型
     * @return int整型
     */
    public int minEatTimes(int[] weights, int totalWeight) {
        Integer[] arr = new Integer[weights.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = weights[i];
        }
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        int[][] dp = new int[arr.length + 1][totalWeight + 1];
        boolean[][] visited = new boolean[arr.length + 1][totalWeight + 1];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j <= totalWeight; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = 0;
        visited[0][0] = true;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= totalWeight; j++) {
                visited[i][j] = visited[i - 1][j];
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; arr[i - 1] * k <= j; k++) {
                    visited[i][j] = (visited[i - 1][j - arr[i - 1] * k] || visited[i - 1][j]);
                    if (visited[i][j] != visited[i - 1][j]) {
                        dp[i][j] = Math.min(dp[i - 1][j - k * arr[i - 1]] + k, dp[i][j]);
                    }
                }
            }
        }
        return dp[dp.length-1][totalWeight]==Integer.MAX_VALUE?-1:dp[dp.length-1][totalWeight];
    }
}

本题考察的知识点是动态规划，我们定义了两个二维数组，一个布尔数组，一个整形数组。布尔数组visited[i][j]用来表示前i个物品是否能够选出总重量为j的若干物品，整形数组dp[i][j]用来表示构成总重量为j在前i类物品中需要选择的最小数目是多少。初始化dp[0][0]=0,其他数为整形最大值，visited[0][0]为true，其余为false,然后开始进行状态转移.