codeforces366C Dima and Salad 背包dp

題目連結：戳這裡

題目大意：n個物品，每個物品有a和b兩個屬性，現在要選一些物品，使得a屬性的和是b屬性的和的k倍，求a屬性和的最大值。

題解：将問題變形：将每個物品的重量看做a[i]-k*b[i]，價值看做a[i]，分正負做兩次背包，最終兩個重量相等的背包就是一組可行解。

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int read()
{
	char c;int sum=0,f=1;c=getchar();
	while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
int n,k,ans=-1;
int a[105],b[105],c[105];
int dp1[10005],dp2[10005];
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++)
	a[i]=read();
	for(int i=1;i<=n;i++)
	b[i]=read(),c[i]=a[i]-b[i]*k;
	memset(dp1,-0x3f,sizeof(dp1));
	memset(dp2,-0x3f,sizeof(dp2));
	dp1[0]=dp2[0]=0;
	for(int i=1;i<=n;i++)
	{
		if(c[i]>=0)
		{
			for(int j=10000;j>=c[i];j--)
			dp1[j]=max(dp1[j],dp1[j-c[i]]+a[i]);
		}
		else
		{
			c[i]=-c[i];
			for(int j=10000;j>=c[i];j--)
			dp2[j]=max(dp2[j],dp2[j-c[i]]+a[i]);
		}
	}
	for(int i=0;i<=10000;i++)
	{
		if(!dp1[i] && !dp2[i]) continue;
		else ans=max(ans,dp1[i]+dp2[i]);
	}
	printf("%d\n",ans);
	return 0;
}