Dima and Salad 01背包变形

题意：n件东西，有属性a和属性b。要选取若干件东西，使得∑aj∑bj=k。在这个条件下，问∑aj最大是多少。

将a作为价值，a-k*b作为重量w，w有正有负，dp分成正负，两组求当前重量下的最大价值
dp1和dp2相同时恰好是a/b=k

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f
const int N=1e4+5;
typedef long long ll;
int w[N],v[N],dp1[N],dp2[N],a[N];
int main()
{
    memset(dp1,-inf,sizeof(dp1));
    memset(dp2,-inf,sizeof(dp2));
	int n,m,i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        w[i]=v[i]-m*a[i];
    }
    dp1[0]=dp2[0]=0;
    for(i=1;i<=n;i++)
    {
        if(w[i]>0)
        {
            for(j=10000;j>=w[i];j--)
                dp1[j]=max(dp1[j],dp1[j-w[i]]+v[i]);
        }
        else
        {
            w[i]=-w[i];
            for(j=10000;j>=w[i];j--)
                dp2[j]=max(dp2[j],dp2[j-w[i]]+v[i]);
        }
    }
    int ans=-1;
    for(i=0;i<10000;i++)
    {
        if(dp1[i]==0&&dp2[i]==0)
            continue;
        ans=max(ans,dp1[i]+dp2[i]);
    }
    printf("%d\n",ans);
	return 0;
}