🌟线性dp
🍎解题思路
1.定义f(i, j)含义:在前i个物品中选取,是否能凑出重量j
2.分类讨论:当前状态由哪些状态转移而来?(此处状态只有两种,能凑出or不能凑出)
1)不选当前砝码,那么能否凑出重量j,和选择前i-1个物品,是否能凑出重量j的状态相同
2)选择当前砝码w,假设放到左边重量是+,当前的总重量是j,那么选择此砝码之前的重量是j-w[i],如果前一个状态能够凑出j-w[i],选择了当前砝码放到左边后,此状态必然能凑出重量j,所以f(i, j) |= f(i - 1, j - w[i]);
3)同理,选择当前砝码放到右边:f(i, j) |= f(i - 1, j + w[i]);
3.遍历f(n, 1…m)有多少个能够凑出重量m,输出ans即可
🍭技巧
1.打表更有助于理解dp,以下是样例打表结果:
3
1 4 6
第1轮dp:
重量w: 0 1 2 3 4 5 6 7 8 9 10 11
前0个砝码:1 0 0 0 0 0 0 0 0 0 0 0
前1个砝码:1 1 0 0 0 0 0 0 0 0 0 0
前2个砝码:0 0 0 0 0 0 0 0 0 0 0 0
前3个砝码:0 0 0 0 0 0 0 0 0 0 0 0
第2轮dp:
重量w: 0 1 2 3 4 5 6 7 8 9 10 11
前0个砝码:1 0 0 0 0 0 0 0 0 0 0 0
前1个砝码:1 1 0 0 0 0 0 0 0 0 0 0
前2个砝码:1 1 0 1 1 1 0 0 0 0 0 0
前3个砝码:0 0 0 0 0 0 0 0 0 0 0 0
第3轮dp:
重量w: 0 1 2 3 4 5 6 7 8 9 10 11
前0个砝码:1 0 0 0 0 0 0 0 0 0 0 0
前1个砝码:1 1 0 0 0 0 0 0 0 0 0 0
前2个砝码:1 1 0 1 1 1 0 0 0 0 0 0
前3个砝码:1 1 1 1 1 1 1 1 0 1 1 1
🍇时间复杂度
$O(NM)$
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 200010 ; //M为最大重量,B为偏移量
bool f[N][M]; //前i个物品,分别放在左右两边能否凑出重量为j
int w[N]; //每个砝码的重量
int n, m;
int main()
{
cin >> n;
for(int i = 1;i <= n; i++) cin >> w[i], m += w[i];
f[0][0] = 1; //0个物品,能凑出重量0
for(int i = 1; i <= n; i++) //枚举前i个物品
for(int j = 0; j <= m; j++) //枚举所有可能的重量
//不选当前物品 | 选物品放到右边 | 选物品放到左边
f[i][j] = f[i - 1][j] + f[i-1][abs(j - w[i])] + f[i-1][j + w[i]];
int ans = 0;
for(int i = 1;i <= m; i++)
if(f[n][i])
ans++;
cout << ans;
return 0;
}