一个入门的背包

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

解决方案: 改写dp方程 考虑 $f\left[i\right]f[i]$f[i] 的来源

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

接下来就是一些特判了

同时不难发现 $f\left[i\right]f[i]$f[i] 只与 $f[i-1]f[i-1]$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()
{
    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;
}