--- title: "砝码称重" created: 2025-11-28 tags: - 算法 --- # 砝码称重 ## 题目 [砝码称重](https://www.acwing.com/problem/content/description/3420/) ![[image-11f8a10d.png]] ## 思路分析 根据这个案例提示其实可以发现它也就是个有数量限制的选择模型 即背包问题 只不过现在物品不只是选和不选或者选几个的问题了 而是说 这个物品可以不放 也可以放在左边 记作+ 还可以放在右边 记作- 怎么说呢 案例中 1=1 意为1这个物品放在左边 右边没物品 这时可以称出1这个重量 2=6-4 意为 6这个物品放在左边 4这个物品放在右边 由此称出2这个重量 所以我们完全可以这样表示状态： f(i,j) 使用前i个砝码称出重量不大于j的选法的集合 属性可以是count——前面模板题（求解法数量）时已经研究过了 当属性为count时 f[n][1-m]表示的是所有从前n个数中选 重量为1-m的选法数量 比如f[n][3]它就涵盖了前n个数里选 选出重量为3的所有选法（涵盖5 3 ，7 3，4 3等等等等）所以我最后要看3这个重量能不能被称出来 就只要看f[n][3]是否不等于0即可 是不是这么一回事 其他也是同理 那就意味着 我要求哪些重量能被凑出来 只需要遍历一下f[n][1-m]即可 1-m中不为0就cnt++ 最后很容易就可以得出一个可选出的重量总数 然后就是如何计算出这个状态 因为并不需要天平平衡 只要能放下即可 我们直接简单放左为正 放右为负 f[3][4]表示前3个物品能否构成左边放重量为4的情形，f[3][-4]表示前3个物品是否能构成右边放重量为4的情形. 假设现在要计算f[i][j],i=3,j=−5,w[i]=1 有三种情况 - 前2个物品能够组成右边放重量5的情形——也就是i不放 直接继承答案 - 前2个物品能够组成右边放重量6(w[i]=1 **放在左边**)的情形——i还没放左边 右边价值为的情况 i在左边放了后 就能凑到3，-5 所以从f[i-1][j-w]转移而来 - 前2个物品能够组成右边放重量4(w[i]=1 **放在右边**)的情形——也就是 i还没放右边时 右边价值为4的情况 此时把i放右边就能得到答案 那么就从f[i-1][j+w]转移而来 计算最终答案时，f[n][m]表示左边放m是否可行，f[n][−m]表示右边放−m是否可行，对于可以称出来的重量来说是一样的，所以只要计算1−m 至于能不能放在左或右 只有一个限制条件 因为要满足 -m <= j <= m 所以预留位置也要满足： 1.左：j - w[i] >= -m 2.右：j + w[i] <= m 最后就是一个偏移量的问题了 j在-m带m之间 但是下标不能为负 所以得把它偏移一下 使得-m的情况也>0 能在数组中存下 ![[image-4b4bd7a9.png]] y总的那个属性为bool实质也是一样的 咱计数发现最后不是0的不就相当于他的最后是true吗 把状态计算的+=改成|=即可 只要3种里有一种能达到 就能达到 所以用|| 到最后就是看f[n][1-m]中有多少个true 后面又写了一遍 思路更清晰了 [[7、砝码称重|7、砝码称重]] ## 代码实现 1061 ms ```cpp #include using namespace std; const int N=110,M=2e5+10,B=M/2;//偏移量 int w[N]; int f[N][M]; int n,m; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; m+=w[i]; } //用count作属性 最后得出每种重量的选法数量 不为0即可 for(int i=0;i<=n;i++) f[i][B]=1; for(int i=1;i<=n;i++){ for(int j=-m;j<=m;j++){ f[i][j+B]=f[i-1][j+B]; if(j-w[i]>=-m)//放左边 f[i][j+B]+=f[i-1][j-w[i]+B]; if(j+w[i]<=m)//放右边 f[i][j+B]+=f[i-1][j+w[i]+B]; } } int res=0; //-m和m都是一样的重量 不过在左或者在右罢了 可以直接只看一边 for(int j=1;j<=m;j++){ if(f[n][j+B]) res++; } cout< using namespace std; const int N=110,M=2e5+10,B=M/2;//偏移量 int w[N]; bool f[N][M]; int n,m; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; m+=w[i]; } //用bool当属性 只要三种有一种true就true 用| f[0][B]=true; for(int i=1;i<=n;i++){ for(int j=-m;j<=m;j++){ f[i][j+B]=f[i-1][j+B]; if(j-w[i]>=-m) f[i][j+B]|=f[i-1][j-w[i]+B]; if(j+w[i]<=m) f[i][j+B]|=f[i-1][j+w[i]+B]; } } int res=0; for(int j=1;j<=m;j++){ if(f[n][j+B]) res++; } cout< using namespace std; const int N=110,M=2e5+10; int w[N]; bool f[N][M]; int n,m; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; m+=w[i]; } f[0][0]=true; //发现可以借鉴下面出答案的经验 -m和m完全就是一种情况 //所以直接把-m的情况取个绝对值归到m的情况中去 这样还可以省去偏移量的工作 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ f[i][j]=f[i-1][j]||f[i-1][abs(j-w[i])]||f[i-1][j+w[i]]; //只要有一个非空,f[i][j]就非空 } } int res=0; for(int j=1;j<=m;j++){ if(f[n][j]) res++; } cout<