Educational Codeforces Round 61 (Rated for Div. 2) E 多重背包优化

https://codeforces.com/contest/1132/problem/E

题意

有8种物品,重量是1~8,每种数量是\(cnt[i]\)(1e16),问容量为W(1e18)的背包最多能装多少重量

题解1

多重背包二进制拆分物品转换成01背包,用map来剪枝掉无用的状态

#include<bits/stdc++.h>

#define ll long long

using namespace std;

map<ll,bool>f,g;

ll a[10],W,s[1005],ans;

vector<ll>w;

int main(){

	cin>>W;

	for(ll i=1;i<=8;i++){

		cin>>a[i];

		if(a[i]){

			ans=max(ans,min(W/i,a[i])*i);

			ll num=1;

			while(a[i]>0){

				w.push_back(min(num,a[i])*i);

				a[i]-=min(num,a[i]);

				num*=2;

			}

		}

	}

	sort(w.begin(),w.end());

	reverse(w.begin(),w.end());

	for(int i=w.size()-1;i>=0;i--)s[i]=s[i+1]+w[i];

	f[0]=true;

	for(int i=0;i<w.size();i++){

		g.clear();

		for(map<ll,bool>::iterator it=f.begin();it!=f.end();it++){

			ll x=it->first;

			g[x]=true;

			if(x+w[i]<=W)g[x+w[i]]=true;

		}

		f.clear();

		for(map<ll,bool>::iterator it=g.begin();it!=g.end();it++){

			ll x=it->first;

			if(x+s[i]<ans)continue;

			f[x]=true;

			ans=max(ans,x);

		}

	}

	cout<<ans;

}

题解2

参考:https://blog.csdn.net/qq_37451344/article/details/88860699

设1到8的最小公倍数为lcm,则将lcm/V[i]看成一整份,然后枚举0到lcm/V[i]作为第二维

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll lcm=840;

ll W,a[10],V[10],dp[10][10005],ans;

int main(){

	cin>>W;

	for(int i=0;i<8;i++){

		cin>>a[i];

		V[i]=i+1;

	}

	memset(dp,-1,sizeof(dp));

	dp[0][0]=0;

	for(int i=0;i<8;i++){

	    ll num=lcm/V[i];

		ll end=min(num,a[i]);

		for(int j=0;j<=lcm*8;j++){

			if(dp[i][j]<0)continue;

			for(int k=0;k<=end;k++){

				if(j+k*V[i]<=lcm*8)dp[i+1][j+k*V[i]]=max(dp[i+1][j+k*V[i]],

						dp[i][j]+(a[i]-k)/num);

			}

		}

	}

	for(int i=0;i<=lcm*8;i++){

		if(i>W)break;

		if(dp[8][i]<0)continue;

		ans=max(ans,i+lcm*min(dp[8][i],(W-i)/lcm));

	}

	cout<<ans;

}

巴特西

Educational Codeforces Round 61 (Rated for Div. 2) E 多重背包优化

题意

题解1

题解2

最新文章

热门文章