蒟蒻求问蒟蒻题
查看原帖
蒟蒻求问蒟蒻题
261262
WaltVBAlston楼主2021/7/7 18:17

请问这样写分组背包为什么会写挂?查了很久也不知道,对了题解看,好像除了纯数据的方式不一样其他都一样,就离谱?

#include<iostream>
using namespace std;
struct pack{
	int u;
	int w;
};
pack a[1005][1005];
int p[1005],n,m,dp[1005],b[1005],tot=0;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int k,l;
		cin>>k>>l>>p[i];
		b[p[i]]++;
		a[p[i]][b[p[i]]].u=k;
		a[p[i]][b[p[i]]].w=l;
	}
	while(1){
		if(a[tot+1][1].u==0)
			break;
		else
		    tot++;
	}
	for(int i=1;i<=tot;i++){
		for(int k=1;k<=b[i];k++){
			for(int j=m;j>=a[i][j].u;j--){
				dp[j]=max(dp[j],dp[j-a[i][k].u]+a[i][k].w);
			}
		}
	}
	cout<<dp[m];
	return 0;
}
2021/7/7 18:17
加载中...