递归法求01背包问题

背包问题全类型背包问题给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。

背包问题⼤体都可以⽤上述⽅式进⾏描述，但在具体的问题上有了不同的限制条件，于是便有了各种类型的背包问题。

背包问题可基本分为0-1背包问题、部分背包问题、多重背包问题、完全背包问题四⼤类。

接下从四种问题的解决的核⼼算法可以把部分背包问题单独化为⼀类，其核⼼算法为贪⼼。

其余的三种背包问题都可以⽤动态规划解决。

造成部分背包问题与其他的背包问题最⼤不同的原因是其限定条件的不同，部分1. 部分背包问题限定条件：每件物品可以只选取⼀部分完整问题描述：有 n 件物品，第i件物品重 w[i]，价值为 v[i]，且每件物品可以进⾏分割，分割后的价值按取⾛重量占该物品总重量的⽐值计算。

在不超过最⼤承载量 C 的范围内，问最⼤可以取⾛的价值为多少？( 其中 i ∈ {1,2,3,···,n} )算法：贪⼼分析：根据本题的特殊性，我们可以任意地对某⼀部品进⾏分割，所以我们优先选择性价⽐⾼的物品，即单位重量下物品的价值。

解题代码//C++#include<cstdio>#include<algorithm>#include<iostream>using namespace std;struct bag { int w,v; //w表⽰重量 v表⽰价值 double p; //⽤来储存v/w 性价⽐}a[10005];bool cmp(bag x,bag y) { return x.p > y.p; //性价⽐⾼的物品排在前⾯}int main() {剩余 } } printf('%.2f\n', ans); //输出答案 return 0;}注意计算时注意数据类型在计算“性价⽐”的时候要注意，在C/C++等⼀部分语⾔中存在以下机制 int/int = int ，这样是⽆法计算出⼩数的，需要将其中任意⼀项浮点化即可。

递归算法得优缺点：3优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法得正确性，因此它为设计算法、调试程序带来很大方便。

3缺点：递归算法得运行效率较低，无论就是耗费得计算时间还就是占用得存储空间都比非递归算法要多。

边界条件与递归方程就是递归函数得二个要素应用分治法得两个前提就是问题得可分性与解得可归并性以比较为基础得排序算法得最坏倩况时间复杂性下界为0(n I o g2n)。

回溯法以深度优先得方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先得方式搜索解空间树T。

舍伍德算法设计得基本思想：设A就是一个确定性算法，当它得输入实例为x时所需得计算时间记为tA(x)。

设Xn就是算法A得输入规模为n得实例得全体，则当问题得输入规模为n时，算法A所需得平均时间为这显然不能排除存在x€Xn使得得可能性。

希望获得一个随机化算法B，使得对问题得输入规模为n得每一个实例均有拉斯维加斯(Las Vegas )算法得基本思想：设p(x)就是对输入x调用拉斯维加斯算法获得问题得一个解得概率。

一个正确得拉斯维加斯算法应该对所有输入x均有p(x)>0。

设t(x)就是算法obst in ate找到具体实例x得一个解所需得平均时间，s(x)与e(x)分别就是算法对于具体实例x求解成功或求解失败所需得平均时间，则有：解此方程可得：蒙特卡罗(Monte Carlo)算法得基本思想：设p就是一个实数，且1/2<p<1。

如果一个蒙特卡罗算法对于问题得任一实例得到正确解得概率不小于p,则称该蒙特卡罗算法就是p正确得，且称p1/2就是该算法得优势。

如果对于同一实例，蒙特卡罗算法不会给出2个不同得正确解答，则称该蒙特卡罗算法就是一致得。

线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。

单纯形算法得特点就是：(1) 只对约束条件得若干组合进行测试，测试得每一步都使目标函数得值增加；(2) 一般经过不大于m或n次迭代就可求得最优解。

完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN） 的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得 出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如 何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关 的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令 f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程， 像这样：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。这跟01背包问题一样有O(N*V）个状态需要求解，但求解每个状态的 时间则不是常数了，求解状态f[v]的时间是O(v/c），总的复杂度是超过O(VN）的。
背包问题已经研究了一个多世纪，早期的作品可追溯到1897年 数学家托比亚斯·丹齐格（Tobias Dantzig， 1884-1956）的早期作品 ，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
应用
1998年的石溪布鲁克大学算法库的研究表明，在75个算法问题中，背包问题是第18个最受欢迎，第4个最需 要解决的问题（前三为后kd树，后缀树和bin包装问题）。
基础背包
题目 基本思路
空间复杂 示例程序
递归实现 程序
测试数据 总结
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些 物品的重量总和不超过背包容量，且价值总和最大。

c语言算法--贪婪算法---0/1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。

从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。

对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。

约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。

在这个表达式中，需求出xt 的值。

xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。

0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。

货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。

例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。

店中有n 种不同的货物。

规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。

你的目标是使车中装载的物品价值最大。

当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。

这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。

0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。

在每一步过程中利用贪婪准则选择一个物品装入背包。

一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。

这种策略不能保证得到最优解。

例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。

当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。

而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。

另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。