[数据结构与算法]Java解洛谷P2347 [NOIP1996 提高组] 砝码称重，包含完整的多重背包状态转移方程，大量注释，通俗易懂

01.题目及链接

题目链接：https://www.luogu.com.cn/problem/P2347

02.多重背包状态转移方程说明

了解多重背包

有 N 种物品和一个容量是 V 的背包，每种物品都有n[i]可用。第 i 种物品的重量是 w[i] 、价值是 v[i]。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

状态转移方程

定义状态dp[i]:背包两种容量分别为j的情况下，物品的最大价值

	for (int i = 1; i <= n; i++)   //有N种物品
		for (int j = v; j>=0; j--) 	//容量v
			for (int k = 1; k <= n[i]; k++)    //第i个物品的数量为n[i]
				if(j>=k*w[i])   dp[j]=Math.max(dp[j], dp[j-k*w[i]]+k*v[i]);

或

		for (int i = 1; i <= n; i++) //有N种物品
			for (int k = 1; k <= n[i]; k++)  //第i个物品的数量为n[i]
				for (int j = v; j >= w[i]; j--) //容量v
					dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]);

03.具体代码

思路1：恰好装满的01背包

	public static void main(String[] args) {
		int[][] input = new int[7][2];
		Scanner in = new Scanner(System.in);
		input[1][0] = 1; input[2][0] = 2; input[3][0] = 3;
		input[4][0] = 5; input[5][0] = 10;input[6][0] = 20;
		int sum = 0;int num = 0;
		Set<Integer> set = new HashSet<>();
		for (int i = 1; i <= 6; i++) {
			input[i][1] = in.nextInt();
			sum += input[i][0] * input[i][1];
			num+=input[i][1];
		}
		in.close();
		int[] dp = new int[sum + 1];
		int[] data=new int[num+1];
		num=1;
		for (int i = 1; i < input.length; i++) {//转01背包数据
			for (int j = 0; j < input[i][1]; j++) {
				data[num]=input[i][0];
				num++;
			}
		}
		Arrays.fill(dp, Integer.MIN_VALUE);
		dp[0]=0;
		for (int i = 1; i < num; i++) {
			for (int j = sum; j >= data[i]; j--) {
				dp[j]=Math.max(dp[j], dp[j-data[i]]+data[i]);
				if(dp[j]<0) continue;
				set.add(dp[j]);
			}
		}
		System.out.println("Total="+set.size());
	}

思路2：多重背包

public static void main(String[] args) {
		int[][] data = new int[7][2];
		Scanner in = new Scanner(System.in);
		data[1][0] = 1;data[2][0] = 2;data[3][0] = 3;
		data[4][0] = 5;data[5][0] = 10;data[6][0] = 20;
		int sum = 0;
		for (int i = 1; i <= 6; i++) {
			data[i][1] = in.nextInt();
			sum += data[i][0] * data[i][1];
		}
		in.close();
		boolean[] dp=new boolean[sum+1];//dp[i]=true表示i可以被表示
		dp[0]=true;
		int num=0;
		for (int i = 1; i <= 6; i++) {
			for (int j = 1; j <= data[i][1]; j++) {
                  //逐一在原有dp的基础上尝试每一个砝码
				for (int k = sum; k>= 0; k--) {
					//可以表示dp[k]，则一定可以表示dp[k+data[i][0]]
					if(dp[k]) dp[k+data[i][0]]=true;
				}
			}
		}
		
		for (int i = 1; i <= sum; i++) {
			if(dp[i]) num++;
		}
		System.out.println("Total="+num);
	}