DP(背包问题) - 砝码称重 - 第十二届蓝桥杯省赛第一场C++A/B组

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∑n​Wi​

① 、 不 选 第 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;
}
上一篇:[NOIP2020]移球游戏


下一篇:php上传2M以上文件限制问题