题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

ysDP

算法思路

    每个砝码都有三种选择:不选,选天平的两侧.本质上是有限制的选择问题--背包问题.
    dp
        状态表示
            dp[i][j]
            集合:从前i个物品选,且总重量为j的所有方案
            属性:bool 集合是否存在
        状态划分
            根据最后一步,第i个物品的选择划分
            1)不选i
                那么子集合为从1~i-1中选且总重量为j的所有方案是否存在:dp[i-1][j]
            2)选w[i]
                确定部分:选i个物品重量w[i],现在求前i-1个物品是否能选j-w[i]的重量:dp[i-1][j-w[i]]
            3)选-w[i]
                dp[i-1][j+w[i]]
        注意j会出现负数,我们可以给j统一加上一个偏移量.

时间复杂度

状态个数 * 状态转移 = nW * 1 = O(nW)

C++ 代码

#include<iostream>

using namespace std;

const int N = 110, M = 2e5 + 10, B = 1e5 + 10; //B 偏移量

int  n, m;//m为所有砝码总重量
int  w[N];
bool dp[N][M];

int main()
{
    cin >> n;
    for( int i = 1; i <= n; i++ )   cin >> w[i], m += w[i];

    dp[0][B] = true;//边界 前0个物品可以构成重量0
    for( int i = 1; i <= n; i++ )
    {
        for( int j = -m; j <= m; j++ )
        {//j最小可以构成-m
            dp[i][j+B] = dp[i-1][j+B];
            if( j-w[i] >= -m )  dp[i][j+B] |= dp[i-1][j-w[i]+B];
            if( j+w[i] <= m )   dp[i][j+B] |= dp[i-1][j+w[i]+B];
        }
    }

    int res = 0;
    for( int j = 1; j <= m; j++ )
    {
        if( dp[n][j+B] )    res++;
    }
    cout << res << endl;

    return 0;
}

C++ 代码

/* 
 *  也可以先考虑选择wi或者不选的情况,在考虑选择-w[i]或者不选的情况
 *  这时两次考虑都是单调的 所以可以简化为一维,不用加上偏移量
 */
#include<iostream>

using namespace std;

const int N = 110 , M = 1e5 + 10;

int n, m;
int w[N];
bool dp[M];

int main()
{
    cin >> n;
    for( int i = 1; i <= n; i++ )   cin >> w[i], m += w[i];

    dp[0] = true;
    for( int i = 1; i <= n; i++ )
    {
        for( int j = m; j >= w[i]; j-- )
        {
            dp[j] |= dp[j-w[i]];
        }
    }

    for( int i = 1; i <= n; i++ )
    {
        for( int j = 0; j + w[i] <= m; j++ )
        {
            dp[j] |= dp[j+w[i]];
        }
    }

    int res = 0;
    for( int j = 1; j <= m; j++ )
    {
        if( dp[j] ) res++;
    }
    cout << res << endl;

    return 0;
}