完全背包问题 一维

参考代码:

import java.util.Scanner;

public class T2132完全背包 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();// 背包容量
		int n = scanner.nextInt();// 物品数量
		int dp[] = new int[m + 1];
		for (int i = 0; i < n; i++) {
			int w = scanner.nextInt();
			int c = scanner.nextInt();
			for (int j = m; j >= w; j--) {
				for (int j2 = 0; j2 * w <= j; j2++) {
					dp[j] = Math.max(dp[j], dp[j - w * j2] + j2*c);
				}
			}
		}
		System.out.println("max="+dp[m]);
	}
}