题解：AcWing 3417 砝码称重

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing3417. 砝码称重 - AcWing题库【题目描述】你有一架天平和N NN个砝码这N NN个砝码重量依次是W 1 , W 2 , ⋅ ⋅ ⋅ , W N W_1,W_2,⋅⋅⋅,W_NW1​,W2​,⋅⋅⋅,WN​。请你计算一共可以称出多少种不同的正整数重量注意砝码可以放在天平两边。【输入】输入的第一行包含一个整数N NN。第二行包含N NN个整数W 1 , W 2 , W 3 , ⋅ ⋅ ⋅ , W N W_1,W_2,W_3,⋅⋅⋅,W_NW1​,W2​,W3​,⋅⋅⋅,WN​。【输出】输出一个整数代表答案。【输入样例】3 1 4 6【输出样例】10【解题思路】![[Pasted image 20260610161143.png]]【算法标签】#01背包【代码详解】#includebits/stdc.husingnamespacestd;constintN105,M100005;// 定义最大物品数N和最大总重量Mintn,m;// 物品数量n总重量mintw[N];// 每个物品的重量boolf[N][M];// 动态规划数组f[i][j]表示前i个物品能否称出重量jintmain()// 主函数{cinn;// 输入物品数量for(inti1;in;i)// 读取每个物品的重量{cinw[i];// 输入第i个物品的重量mw[i];// 累加总重量}f[0][0]1;// 初始状态0个物品可以称出重量0for(inti1;in;i)// 遍历每个物品for(intj0;jm;j)// 遍历所有可能的重量{f[i][j]f[i-1][j];// 不使用第i个物品if(jw[i]m)// 如果将物品放在对侧加在右边{f[i][j]|f[i-1][jw[i]];// 可以从jw[i]转移过来}f[i][j]|f[i-1][abs(j-w[i])];// 如果将物品放在同侧减掉重量}intans0;// 可称出的不同重量数for(intj1;jm;j)// 遍历所有可能的重量for(inti0;in;i)// 遍历所有物品数if(f[i][j])// 如果该重量可以被称出{ans;// 计数加1break;// 跳出内层循环}coutansendl;// 输出可称出的不同重量数return0;// 程序正常结束}【运行结果】3 1 4 6 10