一个入门的背包

但是区别于普通的背包，这个背包可以同时加（或者）减。

解决方案1

每个$a[i]$ 转化为两个 $a[i]于-a[i]$ 这时候就可以用原来的动态转移方程了，注意判断就好了

解决方案2

改写dp方程 考虑$f[i]$的来源

$f[i][j]= \begin{cases} f[i-1][j-a[i]] \ \ \quad \\ f[i-1][j+a[i]]\end{cases}$

只要其中一个可以，那么$f[i][j]$也可以

接下来就是一些特判了

同时不难发现$f[i]$只与$f[i-1]$有关，因此我们可以滚动数组优化空间 （每次循环前记得把要用的滚动数组清空）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

int f[2][2020];
int a[2020];
int n,m,b;

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>b>>m;
	f[0][b]=1;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<=n;i++)
	{
		for(j=m;j>=0;j--)
		{
			if(j-a[i]>=0&&j-a[i]<=m) if(f[(i-1)&1][j-a[i]]) f[i&1][j]=1;
			if(j+a[i]>=0&&j+a[i]<=m) if(f[(i-1)&1][j+a[i]]) f[i&1][j]=1;
		}
		for(j=0;j<=m;j++) f[(i-1)&1][j]=0;
	}
	int ans=-1;
	for(i=0;i<=m;i++)
	if(f[n&1][i]) ans=i;
	cout<<ans<<endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,be,mx;
int c[N];bool dp[N][1010];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>be>>mx;
    for(int i=1;i<=n;i++)cin>>c[i];
     
    memset(dp,0,sizeof(dp));
    dp[0][be]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=mx;j++)
        {
            if(dp[i-1][j]==1)
            {
                if(j+c[i]<=mx)dp[i][j+c[i]]=1;
                if(j-c[i]>=0)dp[i][j-c[i]]=1;
            }
        }
     
    for(int i=mx;i>=0;i--)if(dp[n][i])
    {
        cout<<i<<'\n';
        return 0;
    }
    cout<<"-1\n";
     
    return 0;
}