ZOJ Problem Set - 2071
Mr. Black is a merchant doing technology trading business. He gets orders from his customers and then he analyzes the requests, finding out all the components in need. He then turns to his suppliers to collect those components that he can integrate them to build his own tech-products for sale. Some components can be used for several products so Mr. Black buys them only once. His own products are also unique and sale for once, because his customer would not turn back to buy a same thing twice.
Each product has its own value, though. As well as Mr. Black makes money, so do his suppliers. Hence Mr. Black must choose the set of products he will produce to make out the maximum profit. He may discard some orders in case they can not contribute to his maximum profit.
Now the problem comes to you, his assistant, to find out which orders shall be accepted and what components hence shall be purchased to make out these products, that, Mr. Black can make his maximum profit from them.
One integer specifying how many cases there are to be processed.
For each case:
There will be one blank line above each block and all names contain maximum 32 upper case alphabetic characters.
The number of components will not exceed 250 and there will be no more than 100 orders. All integers are at range [0, 10000].
For each case the following output is required:
One integer telling the maximum profit Mr. Black can make out of his orders,
with such details following:
If several plans have the same maximum profit, any one will be accepted.
Output one blank line between each two consecutive blocks.
Author: Neal Zane
Source: ZOJ Monthly, January 2004