A. 求动态规划0-1背包算法解释
01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物 品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度
以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组 f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procere ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。
有了这个过程以后，01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么 任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。
一个常数优化
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。
由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。
小结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
B. 01背包 动态规划算法
嗯。。。错误上说了嘛，max的第二个参数错了，原参数：V[i-1][j-w[i]]+V[i]，加数V[i]是int*类型的，当然不能和被加数相加啦
C. 用动态规划算法和贪婪算法求解01背包问题的区别
首先这两个算法是用来分别解决不同类型的背包问题的，不存在哪个更优的问题。 当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。 当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。
D. matlab的遗传算法求解0-1整数规划的程序
x = intlinprog(f,intcon,A,b,Aeq,beq)就可以了
用法举例：
Write the objective function vector and vector of integervariables.
f = [-3;-2;-1];
intcon = 3;
Write the linear inequality constraints.
A = [1,1,1];
b = 7;
Write the linear equality constraints.
Aeq = [4,2,1];
beq = 12;
Write the bound constraints.
lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binary
Call intlinprog.
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
E. 用动态规划法解01背包问题的算法时间复杂性
n*m
n是物品数量，m是背包容量的取值范围
F. 线性规划整数解有简便方法吗 线性规划整数解除了用画图法还有什么别的方法有只用代数的方法吗
整数线性规划的解法总结
0-1整数线性规划是整数线性规划的特殊情况,在实际中有着广泛的应用.虽然变量的取值只有两个,但此类问题的求解却意外的困难,下面把有关的一些解法总结一下.
1.穷举法 把所有可能的解一一代入,然后比较满足约束的解,使目标函数最达到最优的解是最优解.这不失为一种方法,但不是一种好方法.如果问题规模大,则无法在可接受的时间内求得最优解.这也是求解整数规划的困难所在.
2.隐枚举法I 是穷举法的改进,其思路是先给出一个可行解,然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）.然后一一检验其它的解,如果该解大于上界或小于下界,则不用检验可行性,因为它不可能是最优解,否则的话就要检验可行性,如果是可行解,则修改上界或下界,继续检验其它的解,否则不用修改上界或下界,直接检验其它的解.这种方法通过上界或下界来控制是否需要进行可行性检验,提高了效率.但是,要找可行解也得花一定的时间,当约束和变量较多时,工作量异常的大,退一步来说,即使可行解比较容易找到,但其产生的上界太大,或是下界太小,则其过滤的效果也不明显.这是这种方法的缺陷.
3.隐枚举法II 这种方法先把问题转化成标准型,然后按照分枝定界法的思想,尽量少的检验可行解来寻找最优解.这种方法比较麻烦,我在这里也描述不清楚,过几天理解透了再来写这一部分.
4.隐枚举法III 这是在程冬时,张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的,大致的思路是：把所有可能的解都代入目标函数算出值,然后把这些目标函数值进行排序,如果是求最大值,则降序排列,如果是求最小值则升序排列.然后按这个顺序一个一个的检验对应的解的可行性,当碰到第一个可行解时即得到最优解,因为其它的解不会优于此解了.这种方法的缺陷也是明显的,如果变量为N个,则需求2的N次个目标函数值,然后还要进行排序,这又是项工作量很大的工作,再一个就是,如果排序结果是把可行解排在最后一个,那还是得进行2的N次方次检验.
4.启发式算法 遗传算法,蚁群算法等都可归于此类.这都是随机算法,说白了就是听天由命,即使算出了最优解你也不知道是不是最优解,因为此类算法的收敛性都只是依概率收敛的,真正在算的过程中是否已得到最优只有上帝知道.启发式算法是万不得已的情况下才使用的,我们用这种方法只能保证得到的解比其它方法得到的好,但不一定就说得到了最优了.
0-1规划的求解方法还在研究之中,也许你会发现一个有效的算法.
G. 多目标线性规划的常用求解算法有哪些
多目标决策主要有以下几种方法：
（1）化多为少法：将多目标问题化成只有一个或二个目标的问题，然后用简单的决策方法求解，最常用的是线性加权和法。
（2）分层序列法：将所有目标按其重要性程度依次排序，先求出第一个最重要的目标的最优解，然后在保证前一目标最优解的前提下依次求下一目标的最优解，一直求到最后一个目标为止。
（3）直接求非劣解法：先求出一组非劣解，然后按事先确定好的评价标准从中找出一个满意的解。
（4）目标规划法：对于每一个目标都事先给定一个期望值，然后在满足系统一定约束条件下，找出与目标期望值最近的解。
（5）多属性效用法：各个目标均用表示效用程度大小的效用函数表示，通过效用函数构成多目标的综合效用函数，以此来评价各个可行方案的优劣。
（6）层次分析法：把目标体系结构予以展开，求得目标与决策方案的计量关系。
（7）重排序法：把原来的不好比较的非劣解通过其他办法使其排出优劣次序来。
（8）多目标群决策和多目标模糊决策等
H. 用动态规划算法怎样求解01背包问题
动态规划主要解决的是多阶段的决策问题。
01背包中，状态为背包剩余的容量，阶段是每一个物品，决策是是否选择当前的物品。
所以用动态规划来解决是非常贴切的。
我们设f[V]表示已经使用容量为V时所能获得的最大价值，w[i]表示i物品的质量，c[i]表示i物品的价值。
for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
这便是所谓的一个状态转移方程。
f[j]表示在已经使用容量为j时的最大价值，f[j-w[i]]表示在已经使用容量为j-w[i]时的最大价值。
f[j]可以由f[j-w[i]]这个状态转移到达，表示选取w[i]这个物品，并从而获得价值为c[i]。
而每次f[j]会在选与不选中决策选出最优的方案。
从每一个物品，也就是每一个阶段的局部最优推出最后的全局最优值。这样就解决了01背包问题
I. MATLAB软件怎样计算0,1规划
最近在折腾01规划，显然lingo在这方面非常的强大，matlab有一个01的规划函数工具，但是是线性函数的，网上很多的。
matlab最近在做题疯了1000*100的01矩阵，matlab经常越界，蒙特卡罗计算时间受不了或者贪心算法只是局部最优。但是lingo就无视了。同学用lingo的很快就搞定了。