上海市计算机学会-天平与砝码（二）

小爱有一座天平，还有 n 个砝码，这些砝码的重量分别为 w_1,w_2,,,,,,,wn​。称重时，砝码与物品可以放在同一边，也可以放在不同边。当砝码与物品放在同一边时，砝码起到了减法的效果。

请计算这些砝码，能够称出多少种重量。

上海市计算机学会竞赛平台 | YACS

根据背包问题的通常做法，是找出状态转移之间的关系，因为这里有个减法，所以会有三个过程。

dp[i][j]表示前i个砝码能否凑成质量j；

能凑成的话， dp[i][j]=dp[i-1][j]

不能凑成，需要再加上第i个砝码才能凑成质量j，dp[i][j]=d[i-1][j+w[i]]

不能凑成，需要减少第i个砝码才能凑成质量j，dp[i][j]=dp[i-1][j-w[i]]

能凑成该质量j，则dp[i][j]=1,不能dp[i][j]=0

dp[i][j]=max(dp[i-1][j],dp[i-1][j+w[i]],dp[i-1][j-w[i]])

最后再遍历质量j，一个个判断能否取得到这些数。

这里给整个砝码预留了位置，这样可以比较好的从i=1开始 理解为第1个砝码，i=0,j=0 没有砝码，没有重量，i=0,j=1、2、3、4 等都是false状态

python的创建一开的列表总有问题，搬运了一个c++，python版本还得多做做01背包练习再来

#include 
using namespace std;
int n,a[105],ans,sum;
bool f[105][100005];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}f[0][0]=true;for(int i=1;i<=n;i++){for(int j=0;j<=sum;j++){f[i][j]=f[i-1][j]||f[i-1][abs(j-a[i])];if(j+a[i]<=sum) f[i][j]=f[i][j]||f[i-1][j+a[i]];}}for(int i=1;i<=sum;i++){if(f[n][i]) ans++;}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！