[size=111%]•阿强是一个汽车运输工，他正在给一项装饰工程运输所需的彩色石头。这些石头的颜色各异，价格也各不相同。有一天阿强突发奇想，他想在一堆彩石中有选择地把彩石装上他的卡车，使得卡车上装载的石头总价值是所有装载方案中最大的。现在有一堆彩石堆放在阿强面前，他知道任何两块石头的颜色都是不同的，但两块颜色不同的石头的重量和价格可能相同。
阿强的卡车总共可装载的重量是W，而且他知道总的彩石的块数，请你帮助阿强确定一个方案，满足阿强的奇想。
输入文件stone.in的第一行是二个整数，依次表示卡车的载重量W和总的彩石块数n，下面共有n行，每行包含二个用空格分隔的整数，依次表示某种颜色彩石的重量和价值。
输出文件stone.out只包含一行一个整数，表示卡车最终装载彩石的最大总价值。
。。。。。。。。。。。。。。。。。。。。。。。
Joy是一位非常出色的汽车维修工，而且他的创业能力也很强，这不，最近他成立了自己的汽车维修110公司，一旦汽车在半途抛锚，只要一个电话，joy就会立刻带着他的工具箱赶到事故地点，为驾驶员朋友维修汽车，由于抢修及时以及维修技术高，汽车维修110公司的生意越来越红火。
但joy是一个追求无止境的人，在生意越做越大的同时，他又动开了新脑筋。他发现无论维修工具箱买得如何大，肯定不能把他公司里所有的维修工具装进去，100％的故障排除率不仅需要精湛的维修技术，如何选择并把最为合适的维修工具装入工具箱，并把工具箱带到故障现场，也是一个非常重要的技巧。由于工具众多，joy无法根据驾驶员报告的故障现象确定最为合适的一些工具，作为朋友的你决定通过程序来帮助joy选择最为合适的工具转入到工具箱中。
当然，joy会事先告诉你一些必要的信息。比如，他的每个工具都是不同的，工具箱的总体积，joy还会告诉你他根据故障特点给每个工具合适程度的效率分数，你的程序必须能确定哪些工具被装入工具箱，并输出总的最大效率分。
输入文件joy.in第一行包含二个整数v和n，分别表示工具箱总体积和所有可供选择的工具的数量。下面共有n行，每行有二个用空格分隔的整数，依次分别表示每个工具的体积大小和joy给定的效率分。
输出文件joy.out包含一个整数，表示在工具箱有限的空间内，所装入的所有工具的效率分数的最大值。
这两道题目。。我感觉似乎一样，都是01背包问题。。
都用动态规划做的。。。
|
发表于 2009-8-15 20:28:56
楼主
发表于 2009-8-16 23:36:52