P1064 Jin Ming's Budget Plan

输入 

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出 

2200

解析

   这道题是一道依赖背包问题,The so-called backpack isi依赖于j,表示若选物品i,则必须选物品j.为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品.

   The title is the attachment dependency and the main component,And the attachment doesn't have an attachment that goes on,So this is a questionThe non-tree dependent knapsack problem.

思路

  我们首先知道,To choose an accessory, you must choose its corresponding main component,Therefore, we must first establish the corresponding relationship between the two,That is, the attachments are placed under the array of the main component：

struct node{
	int v,p,q;
}arr[1001];
vector<node> pri[30222];
int dp[30222],V[60][1000],P[60][100],cnt[60];
int n,m,ans;

cin>>n>>m;
for(int i=1;i<=m;i++)
{
	cin>>arr[i].v>>arr[i].p>>arr[i].q;
	if(arr[i].q>0)
	{
		pri[arr[i].q].push_back(arr[i]);
	}
}

   这样,In fact, we implement the grouping indexed by the main component,Then the next step we need to do is,我们可以Take each set of attachments01背包处理,为什么呢？我们01The purpose of the backpack handling is to draw upon the purchase of this master piece,How do we buy accessories for maximum profit.对于每一个附件,are both cases,To buy and not to buy：

   不买：dp[k]=dp[k]

   买：dp[k]=dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p

   We are for every master piece,都有两种选择,One is to select only the main component,The second is to choose this main piece and some of its accessories

for(int i=1;i<=m;i++)
{
	if(arr[i].q==0)//If it is the main item
	{
		memset(dp,-1,sizeof(dp));//Just the right padding for a backpack
		dp[0]=0;//Just the backpack
		for(int j=0;j<pri[i].size();j++)//Cycle through all attachment counts for the current master
		{
			//01Backpack template idea,But here is fromn-arr[i]开始,Because the premise that we can buy these accessories is to buy the corresponding main parts firstarr[i]
			for(int k=n-arr[i].v;k>=pri[i][j].v;k--)
			{
				//这里也就是dp[k]=max(dp[k],dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p)
				if(dp[k]<dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p&&dp[k-pri[i][j].v]!=-1)//The premise isdp不等于-1,That is, there are just enough to buy
				{
					dp[k]=dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p;
				}
			}
		}
		//And then since we need to recreate every time we loopmemset一下dp数组,所以要保存一下dp状态
		for(int j=0;j<=n-arr[i].v;j++)
		{
			if(dp[j]!=-1)//Just the judgement of the backpack
			{
				cnt[i]++;
				V[i][cnt[i]]=j+arr[i].v;//信息1
				P[i][cnt[i]]=arr[i].v*arr[i].p+dp[j];//信息2
			}
		}
	}
	if(arr[i].q==0)//信息3   只买主件
	{
	    cnt[i]++;
	    V[i][cnt[i]]=arr[i].v;
	    P[i][cnt[i]]=arr[i].v*arr[i].p;
	} 
}

Two pieces of information in the note：

   前提：cnt[i]is the main piecei的所有组合数量,Note that the combined quantity is not an attachment,因为01The problem that the backpack solves is when each item can only be taken once,Different multiple items can be selected,How to combine to get the most value.such as mainA有附件B、C,So if the price is affordable,Possible combinations areA+B、A+C、A+B+C

   信息1：Our previous loop is from 0~n-arr[i],Because at this time we need to select the main part and its accessories,所以我们Store the sum of the prices of several accessories paired with the main unit in V数组里面,相当于上面A+Bprice orA+C、A+B+C.This sentence needs to be understood,Because the knapsack problem is to store all the state in the array,并且j+arr[i].v的范围是从arr[i].v~n,That is, the price of the current main item to the total price

   信息2：Stored here is the purchase of the current master(arr[i].v*arr[i].p)and attachments to the current master(dp[j])的最大价值和

   信息3：Here is the state of buying only the main piece.所以VThe array only needs to store the price of the current master,PThe array just stores the value of the current master

最后,我们需要做的是分组背包的计算,The basic idea is to loop through each main component,in all price ranges,也就是j：0~n的范围下,For every affordable pricej,Cycle through all combinations of the current master,然后maxChoose this combination(dp[j-V[i][k]]+P[i][k])Great value or not(dp[j])比较大.

memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++)
{
	for(int j=n;j>=0;j--)
	{
		for(int k=1;k<=cnt[i];k++)
		{
			if(j>=V[i][k])
			{
				dp[j]=max(dp[j],dp[j-V[i][k]]+P[i][k]);
			}
		}
	}
}

There is no judgment here whether it is the main component,Because if it is an attachment,他的cnt[i]就会是0,所以直接跳过了

最后,只要在dpFind the largest value in the array

for(int i=0;i<=n;i++)
{
	ans=max(ans,dp[i]);
}
cout<<ans<<endl;

Paste the total code：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cstring>
#include <algorithm>
using namespace std;
struct node{
	int v,p,q;
}arr[1001];
vector<node> pri[30222];
int dp[30222],V[60][1000],P[60][100],cnt[60];
int n,m,ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>arr[i].v>>arr[i].p>>arr[i].q;
		if(arr[i].q>0)
		{
			pri[arr[i].q].push_back(arr[i]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(arr[i].q==0)//If it is the main item
		{
			memset(dp,-1,sizeof(dp));//Just the right padding for a backpack
			dp[0]=0;//Just the backpack
			for(int j=0;j<pri[i].size();j++)//Cycle through all attachment counts for the current master
			{
				//01Backpack template idea,But here is fromn-arr[i]开始,Because the premise that we can buy these accessories is to buy the corresponding main parts firstarr[i]
				for(int k=n-arr[i].v;k>=pri[i][j].v;k--)
				{
					//这里也就是dp[k]=max(dp[k],dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p)
					if(dp[k]<dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p&&dp[k-pri[i][j].v]!=-1)//The premise isdp不等于-1,That is, there are just enough to buy
					{
						dp[k]=dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p;
					}
				}
			}
			//And then since we need to recreate every time we loopmemset一下dp数组,所以要保存一下dp状态
			for(int j=0;j<=n-arr[i].v;j++)
			{
				if(dp[j]!=-1)//Just the judgement of the backpack
				{
					cnt[i]++;
					V[i][cnt[i]]=j+arr[i].v;//信息1
					P[i][cnt[i]]=arr[i].v*arr[i].p+dp[j];//信息2
				}
			}
		}
		if(arr[i].q==0)//只买主件
		{
			cnt[i]++;
			V[i][cnt[i]]=arr[i].v;
			P[i][cnt[i]]=arr[i].v*arr[i].p;
		} 
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=0;j--)
		{
			for(int k=1;k<=cnt[i];k++)
			{
				if(j>=V[i][k])
				{
					dp[j]=max(dp[j],dp[j-V[i][k]]+P[i][k]);
				}
			}
		}
	}
	for(int i=0;i<=n;i++)
	{
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	system("pause");
	return 0;
}