算法-动态规划--砝码称重

题目描述

你有一架天平和 N 个砝码, 这 N 个砝码重量依次是 1,2,⋯ ,W1​,W2​,⋯,WN​ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N 。

第二行包含 N 个整数: 1,2,3,⋯ ,W1​,W2​,W3​,⋯,WN​ 。

输出格式

输出一个整数代表答案。

输入输出样例

输入 #1复制

3
1 4 6

输出 #1复制

10

说明/提示

【样例说明】

能称出的 10 种重量是: 1、2、3、4、5、6、7、9、10、111、2、3、4、5、6、7、9、10、11 。

1=1，2=6−4( 天平一边放 6, 另一边放 4) ，3=4−1，4=4，5=6−1，6=6，7=1+6，9=4+6−1，10=4+6，11=1+4+6

【评测用例规模与约定】

对于 50%50% 的评测用例, 1≤N≤15 。

对于所有评测用例, 1≤N≤100,N 个砝码总重不超过 10^5。

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n + 1];
		int sum = 0;
		for(int i = 1;i <= n;i++) {
			arr[i] = scanner.nextInt();
			sum += arr[i];
		}
		int[] dp = new int[sum + 1];
		//dp[j]是砝码是否可以称出j重量，可以为1，不可以为0
		int ans = 0;
		dp[0] = 1;//即什么也不放
		for(int i = 1;i <= n;i++) {//放在同一侧
			for(int j = dp.length - 1;j >= arr[i];j--) {
				if(dp[j - arr[i]] == 1 && dp[j] == 0) {
					dp[j] = 1;
					ans++;
				}
			}
		}
		for(int i = 1;i <= n;i++) {//放在不同侧
			for(int j = 1;j <= sum - arr[i];j++) {
				if(dp[j + arr[i]] == 1 && dp[j] == 0) {
					dp[j] = 1;
					ans++;
				}
			}
		}
		System.out.print(ans);
	}
}

题解分析：这里的dp数组与之前题目中的dp数组不同，这里的dp[j]表示这些砝码是否可以称出重量j，如果是则dp[j] = 1,否则dp[j] = 0。那这与动态规划又有什么关系？我们假设此时有个重量j，那么dp[j]是否为1，一定是取决于dp[j - arr[i]]是否为1，只有dp[j - arr[i]]这个重量是存在的，那么才有放置arr[i]后j重量的出现，这里现在的状态取决于之前的状态体现了动态规划的思想。

动态规划五部曲

1.dp数组以及其下标的含义：dp[j]表示是否可以称出质量j，可以为1，不可以为0

2.递推公式：因为把砝码放在天平的同一侧和不同侧是完全不同的，因此需要分别计算，放在同一侧时：如果未放砝码arr[i]时的质量存在，那么放入砝码后的质量存在，即若有dp[j + arr[i]] == 1，那么dp[j] = 1;同理，放在不同侧时，若未放砝码arr[i]时质量dp[j + arr[i]] == 1，则dp[j] = 1.

3.dp数组如何初始化：放第一个砝码时需要知道未放砝码时的dp，未放砝码即质量为0，可以称出初始化dp[0] = 1。

4.遍历顺序：外层循环遍历砝码，内层循环遍历重量。需要注意的是若砝码放在同一侧，内层循环应该从后往前，若砝码放在不同侧，内层循环应该从前往后。

5.打印dp数组：用于debug自查代码