信息学奥赛一本通T1268-完全背包问题(两种写法)

代码:

二维数组写法:

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();// 背包容量
		int b = scanner.nextInt();// 物品数量
		int abs[][] = new int[b + 1][a + 1];
		int wp[][] = new int[b + 1][2];
		for (int i = 1; i <=b; i++) {
			wp[i][0] = scanner.nextInt();// 体积
			wp[i][1] = scanner.nextInt();// 价值
		}
		for (int i = 1; i <= b; i++) {
			for (int j = 1; j <= a; j++) {
				if (wp[i][0] > j) {
					abs[i][j] = abs[i - 1][j];
				} else {
					abs[i][j] = Math.max(abs[i - 1][j], wp[i][1]
							+ abs[i][j - wp[i][0]]);
				}
			}
		}
		System.out.println("max=" + abs[b][a]);
	}
}

一维数组写法:

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int abs[] = new int[a + 5];
		for (int i = 1; i <= b; i++) {
			int m = scanner.nextInt();// 体积
			int n = scanner.nextInt();// 价值
			for (int j = m; j<=a; j++) {
				abs[j] = Math.max(Math.max(j/m*n, abs[j - m] + n), abs[j]);
			}
		}
		System.out.println("max="+abs[a]);
	}
}