c++采药去更改版

点击联系发帖人 时间：2019-07-18 10:16

采药

典型的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）的整数，分别表示采摘某株草藥的时间和这株草药的价值
输出包括一行，这一行只包含一个整数表示在规定的时间内，可以采到的草药的最大总价值

一个简单地0-1褙包问题

有N件物品和一个容量为V的背包。第i件物品的体积是c[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的

如果不放第i件物品那么问题就转化为“前i-1件物品放入容量为v的背包中”，

如果放第i件物品那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，

此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价徝w[i]

你想深入的话建议看背包九讲吧

}

杰西卡魔网络