多重背包 (Java代码）

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int[]dp=new int[m+1];
		for (int i = 0; i < n; i++) {
			int w=sc.nextInt(),
				v=sc.nextInt(),
			    c=sc.nextInt();
			for (int j = 1; j <=c; c-=j,j*=2) {
				for (int k = m; k >=j*w; k--) {
					dp[k]=Math.max(dp[k], dp[k-j*w]+j*v);
				}
			}
			if(c>0)
				for (int k = m; k >=c*w; k--) {
					dp[k]=Math.max(dp[k], dp[k-c*w]+c*v);
				}
		}
		System.out.println(dp[m]);
	}
}