砝码称重(01背包，偏移量)

原题链接：3417. 砝码称重 - AcWing题库

题意：给定数量与各个重量的砝码，天平左右两边都可以放，问最多称多少种正重量

思路

每个砝码选一次，01背包

但是有正负

状态表示

只考虑前i个的情况下能表示的重量

属性为 重量 j 是否存在

状态计算

考虑正负，选中前 i 个能表示的重量可以是 正 也可以是 负，以第 i 个是否选中来分类

可以是 没选，可以是选在左边，可以是选在右边

实现

const int N = 110, M = 200010, B = M / 2;
 
int n, m;
int w[i];
bool f[N][N];
int sum;
 
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> w[i];
		sum += w[i];
	}
 
	f[0][0] = true;
	for(int i = 1; i <= n; i ++)
		for(int j = -sum; j <= sum; j ++)
		{
			f[i][j + B] = f[i-1][j + B];
			if(j - w[i] >= -sum) f[i][j + B] |= f[i-1][j - w[i] + B];
			if(j + w[i] <= sum) f[i][j + B] |= f[i-1][j + w[i] + B];
		}
 
	int ans = 0;
	for(int i = 1; i <= sum; i ++)
		ans += f[n][i];
 
	cout << ans << endl;
 
	return 0;

过了但不是这么写的，思路是先选好只放正数那一边的，再来用已有的正数可能值来减去可以放在左边的砝码，记录新的可能值

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
typedef long long LL;
 
const int N = 1e5 + 10, M = 110;
 
int n;
bool f[M][N];
int a[M];
 
int main()
{
    cin >> n;
    int s = 0;
    for(int i = 1; i <= n ; i ++)
    {
        cin >> a[i];
        //s += v[i];
        f[i][a[i]] = true;
        s += a[i];
    }
     
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= s; j ++)
        {
            f[i][j] = f[i][j] | f[i-1][j];
            //if(j + a[i] <= s) f[i][j] = f[i][j] | f[i-1][j + a[i]];
            if(j >= a[i]) f[i][j] = f[i][j] | f[i-1][j - a[i]];
        }
        
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= s; j ++)
        {
            if(j + a[i] <= s) f[n][j] = f[n][j] | f[n][j + a[i]];
        }
            
    
    LL cnt = 0;
    //for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= s; j ++)
        {
            //cout << f[n][j] << endl;
            cnt += f[n][j];
        }
        
    cout << cnt << endl;
    
    return 0;
}

偏移码与负数的思考很有参考性