【基础背包入门5】金明的预算方案

<p>&nbsp;</p> <p class="MsoNormal" style="text-indent: 21.75pt"><span style="font-family: 宋体">金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：&ldquo;你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过</span><span style="font-family: 'Courier New'">N</span><span style="font-family: 宋体">元钱就行&rdquo;。今天一早<span style="color: blue">，</span>金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：</span></p> <table class="MsoNormalTable" border="1" cellspacing="0" cellpadding="0" style="border-collapse: collapse"> <tbody> <tr> <td valign="top" width="81"> <p class="MsoNormal"><span style="font-family: 宋体">主件</span></p> </td> <td valign="top" width="132"> <p class="MsoNormal"><span style="font-family: 宋体">附件</span></p> </td> </tr> <tr> <td valign="top" width="81"> <p class="MsoNormal"><span style="font-family: 宋体">电脑</span></p> </td> <td valign="top" width="132"> <p class="MsoNormal"><span style="font-family: 宋体">打印机，扫描仪</span></p> </td> </tr> <tr> <td valign="top" width="81"> <p class="MsoNormal"><span style="font-family: 宋体">书柜</span></p> </td> <td valign="top" width="132"> <p class="MsoNormal"><span style="font-family: 宋体">图书</span></p> </td> </tr> <tr> <td valign="top" width="81"> <p class="MsoNormal"><span style="font-family: 宋体">书桌</span></p> </td> <td valign="top" width="132"> <p class="MsoNormal"><span style="font-family: 宋体">台灯，文具</span></p> </td> </tr> <tr> <td valign="top" width="81"> <p class="MsoNormal"><span style="font-family: 宋体">工作椅</span></p> </td> <td valign="top" width="132"> <p class="MsoNormal"><span style="font-family: 宋体">无</span></p> </td> </tr> </tbody> </table> <p class="MsoNormal" style="text-indent: 21.85pt"><span style="font-family: 宋体">如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有</span><span style="font-family: 'Courier New'">0</span><span style="font-family: 宋体">个、</span><span style="font-family: 'Courier New'">1</span><span style="font-family: 宋体">个或</span><span style="font-family: 'Courier New'">2</span><span style="font-family: 宋体">个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的</span><span style="font-family: 'Courier New'">N</span><span style="font-family: 宋体">元。于是，他把每件物品规定了一个重要度，分为</span><span style="font-family: 'Courier New'">5</span><span style="font-family: 宋体">等：用整数</span><span style="font-family: 'Courier New'">1<b><span style="color: black">~</span></b>5</span><span style="font-family: 宋体">表示，第</span><span style="font-family: 'Courier New'">5</span><span style="font-family: 宋体">等最重要。他还从因特网上查到了每件物品的价格（都是</span><span style="font-family: 'Courier New'">10</span><span style="font-family: 宋体">元的整数倍）。他希望在不超过</span><span style="font-family: 'Courier New'">N</span><span style="font-family: 宋体">元（可以等于</span><span style="font-family: 'Courier New'">N</span><span style="font-family: 宋体">元）的前提下，使每件物品的价格与重要度的乘积的总和最大。</span></p> <p class="MsoNormal" style="text-indent: 21.85pt"><span style="font-family: 宋体">设第</span><span style="font-family: 'Courier New'">j</span><span style="font-family: 宋体">件物品的价格为</span><span style="font-family: 'Courier New'">v[j]</span><span style="font-family: 宋体">，重要度为</span><span style="font-family: 'Courier New'">w[j]</span><span style="font-family: 宋体">，共选中了</span><span style="font-family: 'Courier New'">k</span><span style="font-family: 宋体">件物品，编号依次为</span><span style="font-family: 'Courier New'; color: black">j₁</span><span style="font-family: 宋体; color: black">，</span><span style="font-family: 'Courier New'">j₂</span><span style="font-family: 宋体">，&hellip;&hellip;，</span><span style="font-family: 'Courier New'">j_k</span><span style="font-family: 宋体">，则所求的总和为：</span></p> <p class="MsoNormal" style="text-indent: 21.85pt"><span style="font-family: 'Courier New'">v[j₁]*w[j₁]+v[j₂]*w[j₂]+ </span><span style="font-family: 宋体">&hellip;</span><span style="font-family: 'Courier New'">+v[j_k]*w[j_k]</span><span style="font-family: 宋体">。（其中</span><span style="font-family: 'Courier New'">*</span><span style="font-family: 宋体">为乘号）</span></p> <p class="MsoNormal" style="text-indent: 21.75pt"><span style="font-family: 宋体">请你帮助金明设计一个满足要求的购物单。</span></p>

<p>&nbsp;</p> <p class="MsoNormal" style="text-indent: 5.25pt"><span style="font-family: 宋体">输入文件</span><span style="font-family: 'Courier New'">budget.in </span><span style="font-family: 宋体">的第</span><span style="font-family: 'Courier New'">1</span><span style="font-family: 宋体">行，为两个正整数，用一个空格隔开：</span></p> <p class="MsoNormal" style="text-indent: 10.5pt"><span style="font-family: 'Courier New'">N<span>&nbsp; </span>m</span></p> <p class="MsoNormal" style="text-indent: 10.5pt"><span style="font-family: 宋体">（其中</span><span style="font-family: 'Courier New'">N</span><span style="font-family: 宋体">（</span><span style="font-family: 'Courier New'">&lt;32000</span><span style="font-family: 宋体">）表示总钱数，</span><span style="font-family: 'Courier New'">m</span><span style="font-family: 宋体">（</span><span style="font-family: 'Courier New'">&lt;60</span><span style="font-family: 宋体">）为希望购买物品的个数。）</span></p> <p class="MsoNormal" style="text-indent: 10.5pt"><span style="font-family: 宋体">从第</span><span style="font-family: 'Courier New'">2</span><span style="font-family: 宋体">行到第</span><span style="font-family: 'Courier New'">m+1</span><span style="font-family: 宋体">行，第</span><span style="font-family: 'Courier New'">j</span><span style="font-family: 宋体">行给出了编号为</span><span style="font-family: 'Courier New'">j-1</span><span style="font-family: 宋体">的物品的基本数据，每行有</span><span style="font-family: 'Courier New'">3</span><span style="font-family: 宋体">个非负整数</span></p> <p class="MsoNormal" style="text-indent: 10.5pt"><span style="font-family: 'Courier New'">v<span>&nbsp; </span>p<span>&nbsp; </span>q</span></p> <p class="MsoNormal" style="text-indent: 10.5pt"><span style="font-family: 宋体">（其中</span><span style="font-family: 'Courier New'">v</span><span style="font-family: 宋体">表示该物品的价格（</span><span style="font-family: 'Courier New'">v&lt;10000</span><span style="font-family: 宋体">），</span><span style="font-family: 'Courier New'">p</span><span style="font-family: 宋体">表示该物品的重要度（</span><span style="font-family: 'Courier New'">1<b><span style="color: black">~</span></b>5</span><span style="font-family: 宋体">），</span><span style="font-family: 'Courier New'">q</span><span style="font-family: 宋体">表示该物品是主件还是附件。如果</span><span style="font-family: 'Courier New'">q=0</span><span style="font-family: 宋体">，表示该物品为主件，如果</span><span style="font-family: 'Courier New'">q&gt;0</span><span style="font-family: 宋体">，表示该物品为附件，</span><span style="font-family: 'Courier New'">q</span><span style="font-family: 宋体">是所属主件的编号）</span></p>

<p>&nbsp;</p> <p class="MsoNormal" style="text-indent: 5.25pt"><span style="font-family: 宋体">输出文件</span><span style="font-family: 'Courier New'">budget.out</span><span style="font-family: 宋体">只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（</span><span style="font-family: 'Courier New'">&lt;200000</span><span style="font-family: 宋体">）。</span></p>