Dima and Salad

题意：
给出n个物品的ai和bi的值，求在满足所选物品ai之和除以bi之和等于k时ai之和最大为多少？

思路：
将每一个物品的ai看成价值，ai-bi*k看成体积，这样题目就变成了所选物品体积为0时价值最大为多少？给体积一开始就加上一个较大的值来解决下标为负的问题，这样就只是一个简单的01背包问题了。

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;
const int N=105;

string s;
int a[N], b[N];
struct w
{
    int v, w;
} w[N];

int dp[105][300005];

int main()
{
    ll n, k;
    scanf("%lld%lld",&n,&k);
    fill(dp[0],dp[0]+105*100005,-inf);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&b[i]);
        w[i].v=a[i];
        w[i].w=a[i]-b[i]*k;
    }
    int ans=0, base=150000;
    dp[0][base]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=-100000; j<=100000; j++)
        {
            dp[i][base+j]=max(dp[i-1][base+j-w[i].w]+w[i].v,dp[i-1][j+base]);
            if(j==0)
            {
                ans=max(ans,dp[i][base]);
            }
        }
    }
    if(ans==0)
    {
        ans=-1;
    }
    cout << ans << endl;
    return 0;
}