P1064 金明的预算方案（依赖性背包问题）

这道题可以用分组背包来做。

但是分组有两种方式

一种是把主件,主件+附件1，主件+附件2分成一组

组内只能选一个物品

一种是建一颗树，用树形dp的方式去做

第二种更通用，就算物品的依赖关系是森林都可以做

而第一种只限于这道题，因为只有一层关系，所以有特殊解

目前只写了第一种，后面补第二种

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 412;

const int MAXM = 32123;

int f[MAXM], p[MAXN], w[MAXN], fa[MAXN], n, m;

int W[MAXN], P[MAXN], k[MAXN], cnt, N;

void add(int w, int p)

{

	W[N] = w; P[N] = p; k[N++] = cnt;

}

void init()

{

	REP(i, 1, n + 1)

		if(fa[i] == 0)

		{

			add(w[i], p[i]);

			vector<int> son;

			REP(j, 1, n + 1)

				if(fa[j] == i)

					son.push_back(j);

			if(son.size() >= 1) add(w[i] + w[son[0]], p[i] + p[son[0]]);

			if(son.size() >= 2)

			{

				add(w[i] + w[son[1]], p[i] + p[son[1]]);

				add(w[i] + w[son[1]] + w[son[0]], p[i] + p[son[1]] + p[son[0]]);

			}

			cnt++;

		}

}

int main()

{

	scanf("%d%d", &m, &n);

	REP(i, 1, n + 1)

	{

		scanf("%d%d%d", &w[i], &p[i], &fa[i]);

		p[i] *= w[i];

	}

	init();

	REP(r, 0, cnt)

		for(int j = m; j >= 0; j--)

			REP(i, 0, N)

				if(k[i] == r && j - W[i] >= 0)

					f[j] = max(f[j], f[j - W[i]] + P[i]);

	printf("%d\n", f[m]);

	return 0;

}

第二种

大家有没有看到这个代码和选课的树形dp的区别。（选课https://blog.csdn.net/qq_34416123/article/details/82258060）

这道题是选课的简化版，最多只有两个儿子，而且只有三层。

这份代码多了个递归参数体积。选课那题体积都为1，而cnt数组记录的是以i结尾的子树

的节点的个数，也就是体积。

#include<cstdio>

#include<algorithm>

#include<vector>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 112;

const int MAXM = 32123;

int f[MAXN][MAXM], p[MAXN], w[MAXN], n, m;

vector<int> g[MAXN];

void dfs(int u, int k)

{

    REP(i, 0, g[u].size())

    {

        int v = g[u][i];

        FOR(j, 0, k - w[v]) f[v][j] = f[u][j];

        if(k >= w[v]) dfs(v, k - w[v]);

        FOR(j, w[v], k) f[u][j] = max(f[u][j], f[v][j-w[v]] + w[v] * p[v]);

    }

}

int main()

{

    scanf("%d%d", &m, &n);

    FOR(i, 1, n)

    {

        int fa;

        scanf("%d%d%d", &w[i], &p[i], &fa);

        g[fa].push_back(i);

    }

    dfs(0, m);

    printf("%d\n", f[0][m]);

    return 0;

}

巴特西

P1064 金明的预算方案（依赖性背包问题）

最新文章

热门文章

巴特西

P1064 金明的预算方案 （依赖性背包问题）

最新文章

热门文章

P1064 金明的预算方案（依赖性背包问题）