Dima and Salad 题解(01背包变形)

题目链接

题目大意

给你n个物品，每个物品有两个值一个为a，一个为b

要你拿任意的物品使得\(\sum a/ \sum b=k ,且max(\sum a)\)

\(1<=n<=100\; 1<=k=10\; 1<=a[i],b[i]<=100\)

题目思路

一个显然易见的思路设\(dp[i][j]\)为是否有\(\sum a=i\; \sum b=j\)

然后最后复杂度为\(O(1e10)\) 显然不行

所以考虑化简

把这个问题转化为每个物品重量为\(a[i]-k*b[i]\) 价值为\(a[i]\)

转化为变为01背包

然后由于有负数，所以把背包的初始体积平移一下即可

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const int eps=1e-3;
int n,k;
int a[110],b[110];
int dp[110][maxn];
signed main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    int mid=1e5;
    for(int i=0;i<=n;i++){ //初始化为负无穷
        for(int j=0;j<=2e5;j++){
            dp[i][j]=-inf;
        }
    }
    dp[0][mid]=0;
    for(int i=1;i<=n;i++){
        int w=a[i]-k*b[i];
        int v=a[i];
        for(int j=1;j<=2e5;j++){
            if(j>=w&&dp[i-1][j-w]!=-inf){
                dp[i][j-w]=max(dp[i][j-w],dp[i-1][j-w]); //不选
                dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v); //选
            }
        }
    }
    printf("%d\n",dp[n][mid]<=0?-1:dp[n][mid]);
    return 0;
}