DP(背包问题) - 砝码称重 - 第十二届蓝桥杯省赛第一场C++A/B组
题意:
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W 1 , W 2 , ⋅ ⋅ ⋅ , W N W_1,W_2,⋅⋅⋅,W_N W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数: W 1 , W 2 , W 3 , ⋅ ⋅ ⋅ , W N 。 W_1,W_2,W_3,⋅⋅⋅,W_N。 W1,W2,W3,⋅⋅⋅,WN。
输出格式
输出一个整数代表答案。
数据范围
对于 50% 的评测用例,1 ≤ N ≤ 15。
对于所有评测用例,1 ≤ N ≤ 100,N 个砝码总重不超过 105。
输入样例:
3
1 4 6
输出样例:
10
样例解释
能称出的 10 种重量是:1、2、3、4、5、6、7、9、10、11。
1 = 1;
2 = 6 − 4 (天平一边放 6,另一边放 4);
3 = 4 − 1;
4 = 4;
5 = 6 − 1;
6 = 6;
7 = 1 + 6;
9 = 4 + 6 − 1;
10 = 4 + 6;
11 = 1 + 4 + 6。
分析:
有限制的选择问题,即背包问题。
每种物品有3种状态:不选、放左边(权值为正)、放右边(权值为负)。
状态转移方程:
f [ i ] [ j ] : 考 虑 前 i 件 物 品 , 是 否 能 够 称 出 的 质 量 为 j 的 物 品 。 记 : f[i][j]:考虑前i件物品,是否能够称出的质量为j的物品。记: f[i][j]:考虑前i件物品,是否能够称出的质量为j的物品。记:
m = ∑ i = 1 n W i m=\sum_{i=1}^nW_i m=i=1∑nWi
① 、 不 选 第 i 件 物 品 , 则 f [ i ] [ j ] = f [ i − 1 ] [ j ] 。 ①、不选第i件物品,则f[i][j]=f[i-1][j]。 ①、不选第i件物品,则f[i][j]=f[i−1][j]。
② 、 第 i 件 物 品 放 左 边 , 则 f [ i ] [ j ] = f [ i − 1 ] [ j − w [ i ] ] 。 ②、第i件物品放左边,则f[i][j]=f[i-1][j-w[i]]。 ②、第i件物品放左边,则f[i][j]=f[i−1][j−w[i]]。
③ 、 第 i 件 物 品 放 右 边 , 则 f [ i ] [ j ] = f [ i − 1 ] [ j + w [ i ] ] 。 ③、第i件物品放右边,则f[i][j]=f[i-1][j+w[i]]。 ③、第i件物品放右边,则f[i][j]=f[i−1][j+w[i]]。
其 中 j ∈ [ − m , m ] , 为 了 防 止 数 组 越 界 , 我 们 给 j 加 上 偏 移 量 m , 即 j ∈ [ 0 , 2 m ] 。 其中j∈[-m,m],为了防止数组越界,我们给j加上偏移量m,即j∈[0,2m]。 其中j∈[−m,m],为了防止数组越界,我们给j加上偏移量m,即j∈[0,2m]。
最 后 统 计 f [ n ] [ j ] ( j ∈ [ 1 , 2 m ] ) 中 , 能 够 称 出 的 不 同 质 量 的 个 数 。 最后统计f[n][j](j∈[1,2m])中,能够称出的不同质量的个数。 最后统计f[n][j](j∈[1,2m])中,能够称出的不同质量的个数。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110, M = 200010, B = M / 2;
int n, w[N], m;
bool f[N][M];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i], m += w[i];
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 i = B+1; i <= m + B; i ++)
if(f[n][i])
res ++;
cout<<res<<endl;
return 0;
}