金明的预算方案 pascal思路？

金明的预算方案
如果看过普及组试卷就会发现，对应的第二个题目，也是一个样的背景，提高组只是多了个“主件附件”的的关系，如果去掉这一点，就全没区别了。也就成了经典的背包问题了。也就是多了这么一点，考试的时候就晕了。不知道怎么做了。后来才发现是个很简单的dp题目。可惜我当时没做出来。
草率的审题，可能会得到这样的算法：dp，对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是呼，得到如下的动规方程：
f[i,j]:=f[i-1,j];
if (i为主件or i的附件在包中）and (f[i,j]<f[i,j-v]+v*w)
then f[i,j]:=f[i,j-v]+v*w;
我们来分析一下复杂度，空间：dp的阶段为n^2,对与每一个阶段都要记录该状态下在包中的物品有哪些（因为要确定附件的主件是否在包中)，每个阶段的记录都要O(n)的空间，所以总的就是O(n^3)。时间，一个dp，n^2的外层循环，内部用布尔量加个主附件的对应数组，为O(1)，和起来就为O(n^2)的复杂度。
可以看的出，时间的需求为32000*60，不成问题。空间32000*60*60，大约要7.5M的空间，在64M的要求下是完全可以的过的。如果用上题目中的一个很隐秘的条件：“每件物品都是10元的整数倍”，就可以把速度在提高十倍。
细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有0个，1个或2个附件”。这貌似不起眼的一句话，却给我们降低复杂度提供了条件。想一想，为什么题目要对附件的个数做限制呢，明显是在降低难度。
对于一套物品（包含主件，所以的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下5种：
1.一个都不买
2.主件
3.主件＋附件1
4.主件＋附件2
5.主件＋附件1＋附件2
这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的5种购买方法。