砝码称重DP第十二届蓝桥杯省赛第一场C++A/B/研究生组

题目描述
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W₁,W₂,⋅⋅⋅,W_N。

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

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

输入格式
输入的第一行包含一个整数 N。

第二行包含 N 个整数：W₁,W₂,W₃,⋅⋅⋅,W_N。

输出格式
输出一个整数代表答案。

数据范围
对于 50% 的评测用例,$1\le N\le 15$。
对于所有评测用例，$1\le N\le 100$，N 个砝码总重不超过 10⁵。

输入样例：

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。

思路
$dp[i][j]$代表使用前i个砝码的情况下能否凑出重量为j的物品。0代表凑不出，1代表可凑出。
得到$dp$数组后只需要遍历一遍$dp[n][1]$到$dp[n][sum]$有多少种情况能凑出即可。（sum为所有砝码的总重，因为可凑出重量不可能超过总重）

状态转移方程推导
 情况1——不使用第i个砝码
  直接可得$dp[i][j]=dp[i-1][j]$
 情况2——将第i个砝码放在右边
  $dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]])$，注意放在右边是$j-w[i]$。假定天平左端需要称的物品重量为$j$，那么已知第$i$个砝码是一定要放在右边的，所以剩余砝码需要凑出的重量就是$j-w[i]$。同理可推得砝码放在左边的方程。
 情况3——将第i个砝码放在左边
  $dp[i][j]=max(dp[i][j],dp[i-1][jw[i]])$

其实第i个砝码放在哪里对应的是加还是减没搞清楚也不会错反正就一加一减
解法一 y总解法
  因为该解法在砝码放在左边时第二维下标可能是负数，所以第二维整体加一个偏移量让下标合法。
（y总思路真是太清晰力

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 2e5   10;
const int M = (N / 2);
int w[N];
int dp[105][N];
int main()
{
    IOS;
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i  )
    {
        cin >> w[i];
        sum  = w[i];
    }
    dp[0][M] = 1;//加了一个M偏移量
    int ans = 0;
    for (int i = 1; i <= n; i  )
    {
        for (int j = -sum; j <= sum; j  ) //-sum代表砝码全放在左边，sum代表砝码全放在右边
        {
            //只要有一种方案可以凑出来，那么dp[i][j   M]就是1
            dp[i][j   M] = dp[i - 1][j   M];
            if (j - w[i] >= -sum) //特判不存在的情况
                dp[i][j   M] = max(dp[i][j   M], dp[i - 1][j - w[i]   M]);
            if (j   w[i] <= sum) //特判不存在的情况
                dp[i][j   M] = max(dp[i][j   M], dp[i - 1][j   w[i]   M]);
        }
    }
    for (int i = 1; i <= sum; i  )
        if (dp[n][i   M]) //如果这种凑法存在，ans  
            ans  ;
    cout << ans << endl;
    return 0;
}

解法二（不需要偏移量）
总体思路差不多，但是二维的循环有了优化。

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 2e5   10;
const int M = (N / 2);
int w[N];
int dp[105][N];
int main()
{
    IOS;
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i  )
    {
        cin >> w[i];
        sum  = w[i];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i  )
    {
        for (int j = sum; j >= 0; j--) //不能改成从0到sum，会错
        {
            //这里没加特判是因为即使数组越界了值依旧是0，不会对结果造成影响，所以我就懒得写了
            dp[i][j] = max(dp[i - 1][j   w[i]], dp[i - 1][abs(j - w[i])]);
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= sum; i  )
    {
        if (dp[n][i])
            ans  ;
    }
    cout << ans << endl;
    return 0;
}

这篇好文章是转载于：学新通技术网