1064 金明的预算

这道题就是一个依赖性背包，通过主件附件就能看出来
输入的时候处理好主件和附件，把附件归到主件里面，在规划的时候跳过附件处理主件，因为本题只有0，1，2附件这几种情况，因此枚举所有情况跑01背包
所有的背包都是根据01背包进行一个拓展，所以01背包基础一定要好
首先，对于01背包的两种情况：
1.不选，考虑下一个
2.选，背包的容量减去这个物品的代价，加上这个物品的价值
所以对于这道题，也分为五种情况：
1.不选，考虑下一个
2.选并且只选这个主件
3.选这个主件，并且选附件1
4.选这个主件，并且选附件2
5.选这个主件，并且选附件1和附件2
于是状态转移方程就有五个
01背包的转移方程是f[j] = max(f[j],f[j-w[i]]+c[i])
这道题的思路不难，只不过就是操作比较恶心人
-----------------重新------------------------------------
每一个主件都有0 1 2三个附件
1.不选，考虑下一个
2.选并且只选这个主件
3.选这个主件，并且选附件1
4.选这个主件，并且选附件2
5.选这个主件，并且选附件1和附件2
这是五个情况

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZE=32005;
int n,m;
int v,p,q;//v表示价格，p表示重要度，q表示主件
int mw[SIZE],mv[SIZE];//主件重量，主件价值 
int fw[SIZE][3],fv[SIZE][3];
int tot;
int f[SIZE];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>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<=m;i++)
	{
		for(int j=n;j>=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]);//主件和附件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]);//主件和附件2 
			if(j>=mw[i]+fw[i][1]+fw[i][2]) 
			f[j]=max(f[j],f[j-fw[i][1]-fw[i][2]-mw[i]]+mv[i]+fv[i][1]+fv[i][2]);//主件和附件1和附件2 
		}
	 }
	 cout<<f[n]<<endl;
	return 0;
}