• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

动态规划:依赖背包树DP分组背包


Recommended Posts

一个依赖的背包

题目:10。具有依赖性的背包问题-AcWing题库

0i5ak5enrup3803.png

wzupifnpp5t3804.png

想法:

首先构造一个DP二维数组,其中DP[J]代表以I为起点打包一个体积为J的物品时可以得到的最大值,我们从根开始搜索,设值数组为W[],体积数组为V[],搜索到的节点为U,对于节点U,我们初始化一下,DP,I从V到MAXV,因为要加载这个东西U,背包的容量至少要V,最大可以我们初始化。要启动01背包,必须知道这个节点U的所有邻居节点的DP值,所以我们在一个for循环中遍历所有邻居点,对这些点继续DFS。每次DFS后启动01背包,01背包双环,外层是体积,必须是MAXV到V。注意01背包是从大到小的,所以没有后效。但这是一个分组背包,也就是对于这个体积的背包,我可以对它的邻点有很多选择,比如设邻点是X,外圈是I3360 MaxV-V ,那么DP=Max(DP[I-J]DP[X][J]),J是什么意思?注意j的取值范围,内背包最少能提供0容积,最多能提供i-V。因为j-i=V,至少这个背包要贴合这一层的V。这是一款团体背包,经典款。

关键DP代码:

4l00ysyjzhr3805.png

完整代码:

1 #包括牡蛎

2 #包含算法

3 # includevector

4使用命名空间std

5 int n,m,root

6 int DP[110][110];//表示在不超过体积和容量J的情况下,选择U作为子树得到的最大值。

7矢量塔[110];//动态数组存储相邻点

8 int v[110],w[110];

9 void dfs(int u)

10 {

11 for(int I=v;I=m;我)

12 DP=w;//如果选择U,音量不能小于v

13 for(int I=0;我是美国人。size();我)

14 {

15 int s=a;//A 相邻的文章

16个外勤部;

17 for(int j=m;j=v;j-)//音量

18 for(int k=0;k=j-v;K )//决策

19 {

20 dp[j]=max(dp[j],DP[j-k]DP[k]);

21 }

22 }

23 }

24 int main()

25 {

26 CIN nm;

27 for(int I=1;I=n;我)

28 {

29 int p;

30 cin五世同堂;

31如果(p==-1)

32根=I;//存储根的值,然后dfs将从根开始搜索。

其他33个

34 {

35 //在数组a的P层存储P的邻点I。

36个a[p]。push_back(一);

37 }

38 }

39 dfs(根);

40 cout DP[root][m];

41返回0;

42 }

完美通过:

0aftprtorlq3806.png

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now