ARC073D Simple Knapsack

题目大意

给你n个物品，你有一个容量为W的背包，每一个物品都有它的重量和价值，让你从n个中选取若干个，使得总重量不超过背包的上限，而且使得价值最大。

分析

首先我们不难发现由于W很大，所以这并不是一个普通的01背包，但是我们发现由于所有的wi相差很小，所以如果按体积大小分类，所有物品将仅有4类，这样我们就可以枚举美类物品取了多少了，但是这样虽然时间复杂度没问题但空间会炸。于是我们用dpijk表示考虑到了第i个物品，共取了j个，这j个物品的体积和 - w1*j = k，这样我们就可以在满足复杂度的情况下得到总体积了。具体转移见代码。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define sp cout<<"---------------------------------------------------"<<endl

int dp[][][],w[],v[];

int main(){

      int n,m,i,j,k;

      cin>>n>>m;

      for(i=;i<=n;i++)

        scanf("%d%d",&w[i],&v[i]);

      for(i=;i<=n;i++)

        for(j=;j<=i;j++)

          for(k=;k<=*i;k++){

              dp[i][j][k]=max(dp[i][j][k],dp[i-][j][k]);

            if(k>=w[i]-w[])

              dp[i][j][k]=max(dp[i][j][k],dp[i-][j-][k-(w[i]-w[])]+v[i]);

          }

      int ans=;

      for(i=;i<=n;i++)

        for(j=;j<=i*;j++)

          if((long long)i*w[]+j<=(long long)m)

            ans=max(ans,dp[n][i][j]);

      cout<<ans<<endl;

      return ;

}

巴特西

ARC073D Simple Knapsack

最新文章

热门文章