本解题提供一个树遍历的方法，同时考虑附件与主件的约束，考虑预算约束
其中样本：
5个物品，结果空间32，搜索了13个树分支路径
round 13 finished<--------
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0
样本：
30个物品，1G空间，搜索了158,716的树分支路径
18000 30
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
400 5 9
1300 5 9
1400 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1300 5 20
1400 3 0
500 2 0
800 5 0
1400 5 0
300 5 0
1400 3 27
500 2 27
-----Balance Change-----------------
Expense budget maxVal takenItems
10 50 30 1
maxVal:0
-----balance Change: stack print----------
位置 价格 价值 权重 主件位置 附件数 附件1 附件2 主附件平均权重
idx price wghtV wght mPrt xSub sub1 sub2 meanWght
->+0 10 30 3 -1 0 -1 -1 0
-1 20 60 3 4 0 -1 -1 2.33
-2 20 60 3 4 0 -1 -1 2.33
-3 10 20 2 -1 0 -1 -1 0
-4 10 10 1 -1 0 -1 -1 0
maxVal:0
-----step: stack print----------
idx price wghtV wght mPrt xSub sub1 sub2 meanWght
+0 10 30 3 -1 0 -1 -1 0
->-1 20 60 3 4 0 -1 -1 2.33
-2 20 60 3 4 0 -1 -1 2.33
-3 10 20 2 -1 0 -1 -1 0
-4 10 10 1 -1 0 -1 -1 0
5项物品
-----bestPath stack print----------
idx price wghtV wght mPrt xSub sub1 sub2 meanWght
-0 10 30 3 -1 0 -1 -1 0
+1 20 60 3 4 0 -1 -1 2.33
+2 20 60 3 4 0 -1 -1 2.33
-3 10 20 2 -1 0 -1 -1 0
+4 10 10 1 -1 2 -1 2 0
->- - - - - - - - -
30项物品
maxVal:75800
-----bestPath stack print----------
idx price wghtV wght mPrt xSub sub1 sub2 meanWght
+0 1400 7000 5 -1 1 11 -1 0
+1 1400 7000 5 -1 0 -1 -1 0
+2 1400 7000 5 -1 0 -1 -1 0
+3 800 4000 5 -1 0 -1 -1 0
+4 400 2000 5 -1 0 -1 -1 0
+5 300 1500 5 -1 0 -1 -1 0
+6 300 1500 5 -1 0 -1 -1 0
+7 1300 6500 5 20 0 -1 -1 4.86
-8 500 1000 2 0 0 -1 -1 4.21
+9 1300 6500 5 25 0 -1 -1 4.17
+10 1800 7200 4 -1 0 -1 -1 0
+11 1400 4200 3 0 0 -1 -1 4
+12 300 1200 4 -1 0 -1 -1 0
+13 1300 6500 5 18 0 -1 -1 3.96
+14 400 2000 5 18 0 -1 -1 3.44
+15 400 2000 5 25 0 -1 -1 3.33
+16 1400 4200 3 -1 0 -1 -1 0
-17 1400 4200 3 -1 0 -1 -1 0
+18 1400 4200 3 -1 2 -1 14 0
-19 1400 4200 3 -1 0 -1 -1 0
+20 100 300 3 -1 1 7 -1 0
-21 1400 2800 2 4 0 -1 -1 2.67
-22 1800 3600 2 -1 0 -1 -1 0
-23 800 1600 2 -1 0 -1 -1 0
-24 800 1600 2 -1 0 -1 -1 0
+25 500 1000 2 -1 2 -1 15 0
-26 500 1000 2 -1 0 -1 -1 0
-27 500 1000 2 -1 0 -1 -1 0
-28 500 1000 2 -1 0 -1 -1 0
-29 500 1000 2 -1 0 -1 -1 0
->- - - - - - - - -
京公网安备 11010502036488号