⭐️前面的话⭐️

本篇文章介绍来自2021年蓝桥杯真题之砝码称重，考察算法动态规划，0-1背包，set，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2023年4月7日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️砝码称重⭐️

🔐题目详情

砝码称重

💡解题思路

思路1：使用set，进行动态更新，初始化set放入一个0，表示单个砝码的情况，后续将更新的值（加上另一个砝码的值，减去另外一个砝码的值取绝对值）放入set中，进行下一轮更新。

思路2：转化为0-1背包问题
动态规划 0-1背包问题
状态定义：$f[i][j]$ 表示选择前i个砝码，是否能够凑成j
初始化状态：$f[0][0]=true$;
状态转移：面对第$i$件物品有三种选择，一是不选，而是加，三是减取绝对值。
状态转移方程：$f[i][j]=f[i-1][j]|f[i-1][j+w[i]]|f[i-1][abs(j-w[i])]$

这题本人觉得是需要考虑$0$的情况的，但是蓝桥杯官网给的样例均不包含$0$的情况。

🔑源代码

set:java

import java.util.*;
import java.io.*;public class Main {static final Scanner sc = new Scanner(System.in);static final int N = 110;static Set<Integer> set = new HashSet<>();static int n;static int[] w = new int[N];//方法1， 使用set，去重，动态更新public static void main(String[] args) {n = sc.nextInt();for (int i = 1; i <= n; i++) w[i] = sc.nextInt();set.add(0);for (int i = 1; i <= n; i++) {Set<Integer> tmp = new HashSet<>(set);for (int x : tmp) {set.add(w[i] + x);set.add(Math.abs(w[i] - x));}}int ans = set.size() - 1;System.out.println(ans);}
}

0-1背包问题：java

import java.util.*;
import java.io.*;public class Main {static final Scanner sc = new Scanner(System.in);static final int N = 110, M = (int) 1e5 + 10;static boolean[][] f = new boolean[N][M];static int n;static int[] w = new int[N];//方法2， 动态规划 0-1背包问题//状态定义：f[i][j] 表示选择前i个砝码，是否能够凑成j//初始化状态：f[0][0] = true;//状态转移方程：f[i][j] = f[i - 1][j] | f[i - 1][j + w[i]] | f[i - 1][abs(j - w[i])]public static void main(String[] args) {n = sc.nextInt();for (int i = 1; i <= n; i++) w[i] = sc.nextInt();f[0][0] = true;for (int i = 1; i <= n; i++) {for (int j = 0; j + w[i] < M ; j++) {f[i][j] = f[i - 1][j] || f[i - 1][Math.abs(j - w[i])] || f[i - 1][j + w[i]];}}int ans = 0;for (int i = 1; i < M; i++) if (f[n][i]) ans++;System.out.println(ans);}
}

🌱总结

0-1背包变式题。