洛谷 p1064 金明的预算方案

这道题以前写过 但没写出来吧

一个普通的01背包 但是有一些物件需要在买过前置物件后才能购买

所以我们用一个vector来存放该背包与其后置的物件 这样写可以做后置物件多于两个的情况 但多于两个时复杂度会很高 O(n!)的复杂度 正解应该是树形背包了就

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;

#define ll long long 
/*ll read()
{
	ll x=0,f=1;
	char c = getchar();
	while(c>'9' || c<'0'){
		if(c=='-') f = -f;
		c = getchar();
	}
	while(c>='0' && c<='9')
	{
		x = x*10+c-'0' ;
		c = getchar();
	}
	return x*f;
}*/
const int maxn = 65;



vector<int> v[maxn];
vector<int> w[maxn];
int dp[33000];
int n,m;

int main()
{
	int v1,v2,q;
	cin >> n >> m;
	int k=1;
	for(int i=1;i<=m;++i)
	{
		cin >> v1>> v2>>q;
		if(q==0)
		{
			v[k].push_back(v1);
			w[k].push_back(v1*v2);
			k++;
		}
		else
		{
			int len =  v[q].size();
			for(int j=0;j<len;++j)
			{
				v[q].push_back(v1+v[q][j]);
				w[q].push_back(v2*v1+w[q][j]);
			} 
		}
	}
	
	for(int i=1;i<k;++i)
	{
		
		for(int s1=n;s1>=v[i][0];s1-=10)	//十的整数倍
		{
			for(int j=0;j<v[i].size();++j)//可以保证当前状态只被该物件及其后置物件转移过一次
			{
				if(s1>=v[i][j])
					dp[s1] = max(dp[s1],dp[s1-v[i][j]]+w[i][j]);
			}
		}
	}
	cout << dp[n];
	return 0;
}

虽然不难 也有思路但是卡了一些时间 问题在与判断没加等于号
状态转移有问题