装箱问题

    public int boxin (int V, ArrayList<Integer> num) {
        // write code here
        boolean[] dp = new boolean[V+1];
        dp[0] = true;
        for(int x : num) {
            for(int i = V; i >= x; --i) {
                dp[i] = dp[i] || dp[i-x];
            }
        }
        int m = V;
        while(!dp[m]) {
            --m;
        }
        return V - m;
    }

解题思路:

1. 这题与0-1背包问题很相似,能不能直接套用公式?但似乎缺少价值这一参数,以及要求解空间最小

2. 0-1背包追求价值最大,如何设置适当的价值使问题转化?注意到 V - minV是背包中已被占用的最大空间,若用这些空间表示价值,就变成了0-1背包问题

3. 令w=n,c=n求解0-1背包解res,该问题就是V-res