[Acwing] 426.开心的金明 裸01背包 + [luogu]P1064 金明的预算方案 01背包

前言

两个01背包的题

426.开心的金明 P1064 金明的预算方案

426.开心的金明

因为数据范围很小,我们可以直接跑01背包

跑就是了

CODE

void solve()
{
	cin>>m>>n;
	for(int i=1;i>v>>p;
		for(int j = m;j>=v;j--)
		{
			f[j] = max(f[j],f[j-v]+v*p);
		}
	}
	coutm;
	for(int  i =1;i>v>>p>>q;
		
		if(!q){
			mw[i] = v;
			mv[i] = v*p; 
		}else{
			fw[q][0] ++;
			fw[q][fw[q][0]] = v;
			fv[q][fw[q][0]] = v*p;
		}
	}
	
	for(int i = 1;i=mw[i];j --)
		{
			f[j] =  max(f[j],f[j-mw[i]]+mv[i]);
			//买主键的时候
			
			if(j >= mw[i] +fw[i][1])
			f[j] =max(f[j],f[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]);
			
			if(j >= mw[i] +fw[i][2])
			f[j] =max(f[j],f[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]);
			
			if(j>= mw[i]+fw[i][1] +fw[i][2])
			f[j] = max(f[j],f[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]);
			
		}
		cout