题解 | #装箱问题#

import java.util.*;


public class Solution {
    
    public class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param V int整型 
     * @param num int整型ArrayList 
     * @return int整型
     */
    public int boxin(int V, ArrayList<Integer> num) {
        // write code here
        int n = num.size();
        num.sort(new ComparaInteger());
        int[][] remainSpaces = new int[n + 1][V + 1];
        for (int currentSpace = 0; currentSpace <= V; currentSpace++) {
            remainSpaces[0][currentSpace] = currentSpace;
        }
        for (int currentGoods = 1; currentGoods <= n; currentGoods++) {
            int currentGoodsSpace = num.get(currentGoods - 1);
            for (int currentSpace = 1; currentSpace <= V; currentSpace++) {
                remainSpaces[currentGoods][currentSpace] = remainSpaces[currentGoods - 1][currentSpace];
                if (currentGoodsSpace <= currentSpace) {
                    remainSpaces[currentGoods][currentSpace] = Math.min(remainSpaces[currentGoods][currentSpace], remainSpaces[currentGoods - 1][currentSpace - currentGoodsSpace]);
                }
            }
        }
        return remainSpaces[n][V];
    }
}