有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式:
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式:
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。
输入样例:
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
本题数据规模比较大，仍然用三重循环，是会超时的。
解题思路：
如下，对二进制优化方法进行讲解，例如十进制7用二进制表示为（111）。
（111）每一位所对应的十进制数值分别为1，2，4。
由于任何数字都可以由二进制表示，三位二进制数可表示的范围为0~7，所以1，2，4可以组合成0~7中的任意整数（三个数都不取，组合成0）。
同理，对于十进制10可以用1，2，4，8表示，但是这四个数也可以构造10~15，这显然不够最优。那么最后一个数可以由 10 – 1 – 2 – 4 = 3。表示。那么1，2，4，3就可以构造0~10以内的数：
有趣之处：由于1，2，4可以构造出0~7，再加3可以构造出3~10，而0~3也可以由1，2，4构造，是不是所有的余数都可以由前面的数表示呢。
对于所有的整数s,都可以表示为s = 0 + 1 + 2 + 4 +……+2^n+m(余数)
很容易知道这个余数m < 2^(n+1)，那么
只需证明m前面的数能构造出m即可。由二进制的性质，只需证明m前面的数加起来能够大于等于m即可。而m最大值可取2^(n+1)-1。
对m前面的数进行相加sum = 0 + 1+ 2 + 4 + ….+ 2^n。由等比数列求和公式得sum = 2^(n+1) – 1
即sum >= m成立。
即所有整数0~s都可以由s =
0 +
1 + 2 + 4 +……+2^n+m(余数)
中的红色数字构造
既然弄懂上述问题，那么本题的思路也就出来了 。
即第i件物品不管有多少件，都变成上述形式，形成几件新的商品，这样不管要装几件i物品，都能由新物品构造出来此时运用01背包思想本题就迎刃而解了。
理论成立代码如下（朴素版）：
import java.util.*;
public class Main {
public static int N = 20000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
good g[] = new good[N];//N个good类型指针
g[0] = new good();
int n = sc.nextInt();//物品种类
int m = sc.nextInt();//背包体积
int v = 0;
int w = 0;
int s = 0;
int j = 1;//储存新的物品个数
for(int i = 1;i <= n; i++) {
v = sc.nextInt();
w = sc.nextInt();
s = sc.nextInt();
for(int k = 1; k <= s; k = k * 2) {
s = s - k;
g[j] = new good(k * v, k * w);//别忘记给指针分配空间
j++;//用一个扩充一个
}
if(s > 0) {
g[j] = new good(s * v, s * w);
j++;
}
}
j = j - 1;//别忘记最后一个是空指针，得删掉
int f[][] = new int[j + 2][m + 2];//函数f(i,j)
for(int x = 1;x <= j; x++)
for(int y = 0; y <=m; y++) {
f[x][y] = f[x - 1][y];//不装
if(y >= g[x].v)//可以装,别忘记带等号
f[x][y] = Math.max(f[x][y], f[x - 1][y - g[x].v] + g[x].w);//装入
}
System.out.print(f[j][m]);
}
}
class good{//储存必要信息
int v;
int w;
good(int v, int w)
{
this.v = v;this.w = w;
}
good(){}
}