本题做法
- 0-1 背包 DP。
思路
这道题是一道变形的 0-1 背包 DP 好题。
题目中说，砝码可以放在左边，也可以放在右边。我们令左盘的砝码重量始终大于或等于右盘的重量，设左盘的重量为 \(m_l\)，右盘的重量为 \(m_r\)，物品的重量为 \(m_t\)。则有：
\[m_l=m_r+m_t
\]
此时，若我们又要重新放一个重量为 \(m_p\) 的砝码，若放在左盘中，物品的重量就要增加 \(m_p\)；若要把砝码放在右盘中，则物品的重量就要减少 \(m_p\)。
此时我们定义状态 \(dp[i][j]\) 表示在使用前 \(i\) 个砝码的情况下可否乘出重量 \(j\)（是的话为 true，否的话为 false）。通过上面的分析可知，\(dp[i][j]\) 可以由：
\[dp[i-1][j]或dp[i-1][j+w[i]]或dp[i-1][\ |j-w[i|\ ]
\]
转移而来，因为只需要满足上面的 3 项有一项为 true 即可，所以状态转移方程为（其中 \(∨\) 表示逻辑或）：
\[dp[i][j]=dp[i-1][j]∨dp[i-1][j+w[i]]∨dp[i-1][\ |j-w[i]|\ ]
\]
当然，对于特殊情况 \(j=w[i]\) 时，我们可以直接得到：
\[dp[i][j]=\text{true}
\]
代码
#include<bits/stdc++.h>typedef long long ll;
typedef unsigned long long ull;using namespace std;const int N=105;
const int T=1e5+5;int n,w[N],dp[N][T];int main(){cin>>n;for(int i=1;i<=n;i++) cin>>w[i];dp[0][0]=1;for(int i=1;i<=n;i++) {for(int j=1;j<T;j++) {if(j==w[i]) dp[i][j]=1;else{dp[i][j]|=dp[i-1][j];dp[i][j]|=dp[i-1][abs(j-w[i])];if(j+w[i]<T) dp[i][j]|=dp[i-1][j+w[i]];}}} int ans=0;for(int i=1;i<T;i++){if(dp[n][i]) ans++;}cout<<ans<<endl;return 0;
}