砝码称重
题目 砝码称重
思路分析
根据这个案例提示其实可以发现它也就是个有数量限制的选择模型 即背包问题
只不过现在物品不只是选和不选或者选几个的问题了
而是说 这个物品可以不放 也可以放在左边 记作+ 还可以放在右边 记作-
怎么说呢 案例中
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 能在数组中存下
y总的那个属性为bool实质也是一样的
咱计数发现最后不是0的不就相当于他的最后是true吗
把状态计算的+=改成|=即可
只要3种里有一种能达到 就能达到 所以用||
到最后就是看f[n][1-m]中有多少个true
后面又写了一遍 思路更清晰了 7、砝码称重
代码实现
1061 ms
#include<bits/stdc++.h>
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<<res;
return 0;
}
1162 ms
#include<bits/stdc++.h>
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<<res;
return 0;
}
251 ms
#include<bits/stdc++.h>
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<<res;
return 0;
}
💬 评论