acwing5. 多重背包问题 II（二进制优化转成01背包）

有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

000

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 5 1 2 3 2 4 1 3 4 3 4 5 2

输出样例：

10

import java.util.*;
import java.io.*;
public class Main {
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String[] ss = cin.readLine().split(" ");
        int n = Integer.valueOf(ss[0]), m = Integer.valueOf(ss[1]);
        int[] f = new int[m+1];
        List<int[]> list = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            ss = cin.readLine().split(" ");
            int v = Integer.valueOf(ss[0]), w = Integer.valueOf(ss[1]), s = Integer.valueOf(ss[2]);
            for (int j = 1; j <= s; j *= 2) {
                s -= j;
                list.add(new int[]{v * j, w * j});
            }
            if (s > 0) list.add(new int[]{v * s, w * s});
        }
        for (int[] t : list) {
            for (int j = m; j >= t[0]; --j) 
                f[j] = Math.max(f[j], f[j - t[0]] + t[1]);
        }
        System.out.println(f[m]);
    }
}