题解 | #购物单#

/*HJ16购物单
每件物品只买一次:0-1背包问题
先买主件才能买附件
花费不超过N元,求最大满意度 
*/
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int N,m;//总钱数and可购买物品的个数
	cin>>N>>m;
	int temp=0; 
	vector<vector<int> >dp(60,vector<int>(32000,0));
	vector<vector<int> >price(60,vector<int>(3));
	vector<vector<int> >impo(60,vector<int>(3));
	vector<int>cla(60);
	vector<vector<int> >sati(60,vector<int>(3));
	for(int i=0;i<m;i++)
	{
		cin>>price[i][0]>>impo[i][0]>>cla[i];
	}
//	cout<<"satip:"<<endl;
	for(int i=0;i<m;i++)//计算满意度 
	{
		sati[i][0]=impo[i][0]*price[i][0];
//		cout<<sati[i][0]<<endl;
	}
	for(int i=0;i<m;i++)//price二维数组 
	{
		if(cla[i]!=0&&price[cla[i]-1][1]==0) price[cla[i]-1][1]=price[i][0];
		else if(cla[i]!=0&&price[cla[i]-1][1]!=0) price[cla[i]-1][2]=price[i][0];		
	}	
	for(int i=0;i<m;i++)//sati二维数组 
	{
		if(cla[i]!=0&&sati[cla[i]-1][1]==0) sati[cla[i]-1][1]=sati[i][0];
		else if(cla[i]!=0&&sati[cla[i]-1][1]!=0) sati[cla[i]-1][2]=sati[i][0];
	}
	for(int i=0;i<m;i++)//price/sati二维数组修改 ,记得cla一起删啊啊啊啊啊 
	{
		if(cla[i]!=0)
		{
			price.erase(price.begin()+i);
			sati.erase(sati.begin()+i);
			cla.erase(cla.begin()+i);
			i--;
			m--; 
		}		
	}
	for(int i=0;i<m;i++)//便宜的附件放前面 
	{
		int t=0;
		if(price[i][1]>price[i][2]) 
		{
			t=price[i][1];price[i][1]=price[i][2];price[i][2]=t;
			t=sati[i][1];sati[i][1]=sati[i][2];sati[i][2]=t;
		}		
	}	
//	cout<<"price:"<<endl;
//	for(int i=0;i<m;i++)
//	{
//		for(int j=0;j<3;j++)
//		cout<<price[i][j]<<" ";
//		cout<<endl;
//	}
//	cout<<"sati:"<<endl;
//	for(int i=0;i<m;i++)
//	{
//		for(int j=0;j<3;j++)
//		cout<<sati[i][j]<<" ";
//		cout<<endl;
//	}
	/*dp数组初始化*/
	for(int i=0;i<m;i++)//没钱啥满意度也没有 
	{
		dp[i][0]=0;
	} 
	for(int j=1;j<=N;j++)//dp数组第一行初始化 
	{
		if(j>=price[0][0])//够买主件 
		dp[0][j]=sati[0][0];
		if(j>=(price[0][0]+price[0][1])) //够买主件和附件1 
		dp[0][j]=sati[0][0]+sati[0][1];
		if(j>=(price[0][0]+price[0][2]))//够买主件和附件2 或 主件和附件1
		dp[0][j]=sati[0][0]+max(sati[0][1],sati[0][2]);
		if(j>=(price[0][0]+price[0][1]+price[0][2]))//够买主件、附件1、附件2 
		dp[0][j]=sati[0][0]+sati[0][1]+sati[0][2];
	}
	/*dp数组更新*/
	for(int i=1;i<m;i++)
	for(int j=1;j<=N;j++)
	{
		dp[i][j]=dp[i-1][j];
		if(j>=price[i][0])//买得起主件 
		dp[i][j]=max(dp[i-1][j],dp[i-1][j-price[i][0]]+sati[i][0]);
		if(price[i][1]!=0||price[i][2]!=0) //有附件 
		{ 
			if(j>=price[i][0]+price[i][1])//买得起主件和附件1
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]]+sati[i][0]+sati[i][1]);
			}
			
			if(j>=price[i][0]+price[i][2])//买得起主件和附件2或1 
			{
				temp=max(dp[i-1][j-price[i][0]-price[i][1]]+sati[i][0]+sati[i][1],dp[i-1][j-price[i][0]-price[i][2]]+sati[i][0]+sati[i][2]);
				dp[i][j]=max(dp[i][j],temp);
			}		
			if(j>=price[i][0]+price[i][1]+price[i][2])//买得起主件和附件1和附件2 
			dp[i][j]=max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]-price[i][2]]+sati[i][0]+sati[i][1]+sati[i][2]);	
		}		
	}
	cout<<dp[m-1][N]<<endl;
//	cout<<"dp:"<<endl;
//	for(int i=0;i<m;i++)
//	{
//		for(int j=0;j<=N;j++)
//		{
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	} 
}