John wantsto have a journey around Ireland. He has many items that he likes to carry with him, but although he has three suitcases, unfortunately, he cannot accommodate all his itemsin the suitcases. Thus, he needs to decide which items to pick. He knows the size and worth of each item. Therefore, he likes to pick the items so that the total values of the selected items be maximum. There are several items that he cannot take part of them, like his violin. But some of them, he can take part of them like sugar. You need to write a program in Java to help John select his items and tell John that each item should be put in which suitcase. The input of the program is the number of suitcases that John has and also the capacity of each of them. In addition, the total number of the items, the size and worth of each, and whether John can take a part of the item.

好的，这是一个背包问题（Knapsack Problem），我们可以使用动态规划算法来解决。首先，我们需要定义以下几个变量：

- `n`：旅行者带的物品总数
- `m`：旅行者拥有的行李箱数量
- `w[i]`：第 `i` 个物品的体积
- `v[i]`：第 `i` 个物品的价值
- `t[i]`：第 `i` 个物品是否可以分开带（是则为 1，否则为 0）
- `c[j]`：第 `j` 个行李箱的容量
- `f[i][j][k]`：前 `i` 个物品，放置在前 `j` 个行李箱中，第 `k` 个行李箱还剩余的容量时的最大价值

那么，我们可以得到状态转移方程：

- 当第 `i` 个物品不能分开带时，有：

$$
f[i][j][k] = \max \{f[i-1][j][k], f[i-1][j-1][c[j]] + v[i]\}
$$

- 当第 `i` 个物品能分开带时，有：

$$
f[i][j][k] = \max \{f[i-1][j][k], f[i-1][j-1][c[j]] + v[i], f[i-1][j][k-w[i]] + v[i]\}
$$

最终，答案即为 $f[n][m][0]$。具体实现可以参考以下 Java 代码：

public class Knapsack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 物品总数
        int m = scanner.nextInt(); // 行李箱数量
        int[] w = new int[n+1]; // 物品体积
        int[] v = new int[n+1]; // 物品价值
        int[] t = new int[n+1]; // 物品是否可分开带
        int[] c = new int[m+1]; // 行李箱容量
        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
            t[i] = scanner.nextInt();
        }
        for (int i = 1; i <= m; i++) {
            c[i] = scanner.nextInt();
        }
        int[][][] f = new int[n+1][m+1][1001]; // 前 i 个物品，放置在前 j 个行李箱中，第 k 个行李箱还剩余的容量时的最大价值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k <= c[j]; k++) {
                    f[i][j][k] = f[i-1][j][k];
                    if (k >= w[i]) {
                        f[i][j][k] = Math.max(f[i][j][k], f[i-1][j][k-w[i]] + v[i]);
                    }
                }
                if (t[i] == 1) {
                    for (int k = 0; k <= c[j]; k++) {
                        if (k >= w[i]) {
                            f[i][j][k] = Math.max(f[i][j][k], f[i-1][j-1][c[j]] + v[i]);
                        }
                    }
                }
            }
        }
        System.out.println(f[n][m][0]);
        scanner.close();
    }
}