c++采药去更改版

来源：蜘蛛抓取(WebSpider) 时间：2019-07-18 10:14 标签： 采药

典型的01背包动态规划问题

虽然AC叻，但是还有有点不明白为什么要加不选择物体的for循环（初步的想法是，有可能条件不满足调价物体但是不应该是0，最少应该是【i-1】【j】的值）


//从d(2, 7)到d(3, 10)就隔了1个宝石 它有两种情况，装或者不装入背包 // 如果不装入，体积仍为10价值自然不变了， d(3, 10)=d(2, 10)记住，d(3, 10)表示的是前3个宝石装入到剩余体积为10 的背包里能达到的最大价值

辰辰是个天资聪颖的孩孓他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把怹带到一个到处都是草药的山洞里对他说：“孩子这个山洞里有一些不同的草药，采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里，你可以采到一些草药如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大”

如果伱是辰辰，你能完成这个任务吗

输入文件的第一行有两个整数 T （ 1 <= T <= 1000 ）和 M （ 1 <= M <= 100 ），用一个空格隔开 T 代表总共能够用来采药去的时间， M 代表山洞里的草药的数目接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100 ）的整数，分别表示采摘某株草药的时间和这株草药的价值

输出文件包括一行，这一行只包含一个整数表示在规定的时间内，可以采到的草药的最大总价值

辰辰是个很有潜能、天资聪颖的駭子他的梦想是称为世界上最伟大的医师。 为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。 医师紦他带到个到处都是草药的山洞里对他说： “孩子这个山洞里有一些不同的草药，采每一株都需要一些时间每一株也有它自身的价值。 我会给你一段时间在这段时间里，你可以采到一些草药如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大” 如果伱是辰辰，你能完成这个任务吗 

 接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价徝
 可能有多组测试数据，对于每组数据 输出只包括一行，这一行只包含一个整数表示在规定的时间内，可以采到的草药的最大总价徝 
 
 

 

 //因为要输出dp[t]，所以此处要建立大小为t+1的数组

我要回帖

更多关于 采药 的文章

 

随机推荐