题目链接：http://codeforces.com/problemset/problem/366/C
题意：
有n个物品，每个物品有两个属性a[i]和b[i]。
给定k，让你选出一些物品，使得 ∑ a[i] / ∑ b[i] = k。
问你选出物品的 ∑ a[i]最大是多少。
题解：
将原式变形：
∑ a[i] - k * ∑ b[i] = 0
可以看做有一个容积为0的箱子，每个物品的价值为a[i]，体积为a[i] - k*b[i]，问你最大总价值。
这就变成了01背包。
但是体积a[i] - k*b[i]有可能为负值。
所以将体积为正的分一堆，体积为负的分到另一堆。
体积取绝对值，分别跑一遍01背包求出pos数组和neg数组。
pos[i]和neg[i]分别表示用了i的体积，此时的最大总价值。
然后统计答案。
枚举花费体积i，正负相互抵消：ans = max(pos[i] + neg[i])
当ans = 0时说明啥都没选，输出-1。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105
#define MAX_C 100005 using namespace std; int n,k;
int a[MAX_N];
int b[MAX_N];
int pos[MAX_C];
int neg[MAX_C]; void read()
{
cin>>n>>k;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++) cin>>b[i];
} void work()
{
memset(pos,0xc0,sizeof(pos));
memset(neg,0xc0,sizeof(neg));
pos[]=neg[]=;
for(int i=;i<=n;i++)
{
int c=a[i]-k*b[i];
if(c>=)
{
for(int j=MAX_C-;j>=c;j--)
{
pos[j]=max(pos[j],pos[j-c]+a[i]);
}
}
else
{
c=-c;
for(int j=MAX_C-;j>=c;j--)
{
neg[j]=max(neg[j],neg[j-c]+a[i]);
}
}
}
int ans=;
for(int i=;i<MAX_C;i++)
{
ans=max(ans,pos[i]+neg[i]);
}
if(ans) cout<<ans<<endl;
else cout<<-<<endl;
} int main()
{
read();
work();
}