Atcoder regular Contest 073(D - Simple Knapsack)
因为 w1≤wi≤w1+3 这个特殊条件，我们可以将每个重量离散化一下，同时多开一维记录选择的物品数量，因此可以由状态得到此时的实际背包重量.
dp[i][j][k]为考虑前i个物品，背包剩余容量，取了k个物品。此时的实际背包重量为k*w1+j
#include#include #include #include #include #include #include #define ll long long#define inf 1000000000LL#define mod 1000000007using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f;}ll dp[105][305][105],w[105];int v[105];int main(){ // while(true) { int n=read(),V=read(); for(int i=1;i<=n;i++){ w[i]=read();v[i]=read(); if(i>1){ w[i]=w[i]-w[1]; } } memset(dp,0,sizeof(dp)); int w1=w[1]; w[1]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=300;j++){ for(int k=1;k<=n;k++){ if(j>=w[i]) dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-1]+v[i]); else dp[i][j][k]=dp[i-1][j][k]; } } } ll ans=0; for(ll i=0;i<=300;i++){ for(ll j=0;j<=n;j++){ if(j*w1+i<=V){ ans=max(ans,dp[n][i][j]); } } } printf("%I64d\n",ans); } return 0;}