多重背包模板题 这题数据范围给的200 可以用n^3做法不会超时 数据范围为8e8

n^3做法如下

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define ll long long
const int mod=1e9+7;
typedef pair<int,int> PII;
const int N=1007;
int v[N],w[N],s[N];
int dp[N][N];
int n,m;
int a[N];
int v1[N],w1[N];
void solve(){
	int n,t;
	cin>>n>>t; int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>s[i]>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=t;j++){
			for(int k=0;k<=s[i];k++){
				if(j>=k*v[i])
					dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
				
			}
		}
	}
	cout<<dp[n][t];
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	// 		cin>>t;
	while(t--){
		solve();
	}
}

当数据范围为2000时候 整个数据范围就来到了8e11 n^3做法肯定超时

这时候就需要用二进制优化

代码如下

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define ll long long
const int mod=1e9+7;
typedef pair<int,int> PII;
const int N=1007;
int v[N],w[N],s[N];
int dp[N];
int n,m;
int a[N];
int v1[N],w1[N];
void solve(){
	int n,t;
	cin>>n>>t; int cnt=0;
	for(int i=1;i<=n;i++){
		int a,b,s;
		cin>>s>>a>>b;
		int k=1;
		while(k<=s){
			cnt++;
			v[cnt]=k*a;
			w[cnt]=k*b;
			s-=k;
			k*=2;
		}
		if(s>0){
			cnt++;
			v[cnt]=a*s;
			w[cnt]=b*s;
		}
	}
    n=cnt;
	for(int i=1;i<=n;i++){
		for(int j=t;j>=v[i];j--)
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	}
	cout<<dp[t]<<endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
// 		cin>>t;
	while(t--){
		solve();
	}
}