多重背包

userId_undefined

复仇者_零

尊贵铂金

2023-08-10 16:15:39

发布于：浙江

0阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int C,n,w[1010],c[1010],s[1010];
int ww[10100],cc[10100],nn;
int dp[10100][1010];
int main(){
	cin>>C>>n;
	for(int i = 1;i <= n;i++) cin>>w[i]>>c[i]>>s[i];
	for(int i = 1;i <= n;i++){
		int cnt = 1;
		while(s[i] >= cnt){
			s[i] -= cnt;
			ww[++nn] = cnt * w[i];
			cc[nn] = cnt * c[i];
			cnt *= 2;
		}
		if(s[i] == 0) continue;
		ww[++nn] = w[i] * s[i];
		cc[nn] = c[i] * s[i];
	}
	for(int i = 1;i <= nn;i++){
		for(int j = 1;j <= C;j++){
			if(j >= ww[i]) dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - ww[i]] + cc[i]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	cout<<dp[nn][C];
	return 0;
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论