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[110][110][310],w[110],v[110];
int main(){
      int n,m,i,j,k;
      cin>>n>>m;
      for(i=1;i<=n;i++)
        scanf("%d%d",&w[i],&v[i]);
      for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
          for(k=0;k<=3*i;k++){
              dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
            if(k>=w[i]-w[1])
              dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-(w[i]-w[1])]+v[i]);
          }
      int ans=0;
      for(i=1;i<=n;i++)
        for(j=0;j<=i*3;j++)
          if((long long)i*w[1]+j<=(long long)m)
            ans=max(ans,dp[n][i][j]);
      cout<<ans<<endl;
      return 0;
}