⑴ 用分治法处理0-1背包的算法
设有一个背包，可以放入的重量为s。现在n件物品，重量分别为w1,w2,…,wn，并假设wi(1≤i≤n)均为正整数
program kic;
const M=10;{物品的件数}
var
w:array [1..M] of integer;{W[i]—第i件物品的重量}
x,y,i:integer;{x,y—选中的物品的重量和及其件数}
f:boolean; }
function knap(s,n:integer):boolean;
begin
if s=0 then knap:=true
else if (s<0) or ((s>0) and (n<1))
{产生的不合理结果说明方案不可能存在}
then knap:=false
else begin
if knap(s-w[n],n-1)=true {选中物品n}
then begin
writeln('number:',n:4,' weight:',w[n]:4);
knap:=true;
end
else knap:=knap(s,n-1);
{在除物品n外的n-1件物品中递归选择}
end;
end;
begin
fillchar(w,sizeof(w),0);{初始化}
write('object number=');{输入选中的物品的件数}
repeat readln(y); until y<=M;
write('total weight=');{输入选中物品的重量和}
readln(x);
for i:=1 to y do read(w[i]);{输入每物品的重量}
f:=knap(x,y);{递归求解背包问题}
if not(f) then writeln('not find');
{若背包中放不下重量和为X的Y件物品,则输出无解信息}
end.
⑵ 什么是0-1背包问题和背包问题，适用什么算法求解
动态规划、贪心法、回溯法、分支限界法
⑶ 用动态规划算法怎样求解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背包问题
⑷ 求解释01背包问题
这个是状态转移方程
f[v] 表示背包剩余容量V时候积累的价值总和
你这个是优化版本的只用了一维数组 有个更基本的方法我解释给你听
有n件物品 假设当前到第i件了
{ f[i - 1][v];
f[i][v](到第i件时 此时容量为v ) = {
{ f[i - 1][v - w[i]] + p[i];（v>=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]。
⑸ 动态规划的0-1背包问题，请高手解释下代码
这是清华算法设计C++描述上的代码吧？呵呵 我正巧读过。
简单解释一下吧 在解释之前你要知道动态规划是一个自底向上的过程
这个算法用到了一个二维数组m[][] 来存储各个坐标的价值信息 所以横坐标表示背包号码 纵坐标表示背包容量从1到c
注意该算法只能限制c是整数且每个背包的重量也是整数.
然后int jMax=min(w[n]-1,c);找出w[n]-1和 c之间的小者。
for(int j=0;j<=jMax;j++) m[n][j]=0;表示第n个物品不选 那么所以价值为0
for(int j=w[n];j<=c;j++) m[n][j]=v[n];表示第n个物品选择 所以价值为v[n]
for(int i=n-1;i>1;i--){
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
表示自n-1到2逐层计算各m[i][j]的值 每一个m[i][j]的值都是根据上一层也就是m[i][j+1] 得到的 最后处理个第一层的边界条件 m[1][c]就是所得答案了
⑹ 解决0-1背包问题需要排序的有哪些算法
用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然后，将物品的vi/wi的大小进行降序进行排列，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。
⑺ 01背包问题
能不能用性价比来做呢
动态规划看不懂啊
----------------------------------------------------------------------
如果不是0-1问题的话，当然可以通过比较性价比来做，这时候可考虑用贪心算法；但如果是0-1问题的话就不能单纯“用性价比来做”了，因为有可能背包空出一大块。举个简单的例子：一个背包的容量是10KG，
物品A重7KG，价值为14元，
物品B重6KG，价值为11元，
物品C中4KG，价值为7元，
从性价比来看，A最高，但是将A放到背包里以后，无法放进其他物品了，此时总价值为14元；显然，本问题的最佳方案为将B、C放入背包，总价值为18元。
这就是0-1背包问题为什么能用动态规划算法，而不能用贪心算法的原因。共同学习:-D
⑻ 01背包问题，程序求解
把这一句：int f[maxn],t[maxn],v[maxn];
放到main()的前面去，或者定义后就立即赋值为0。
因为局部变量初始化的值是不确定的，但保证全局变量都被初始化为0。
还有你最后：cout<<f[T];这个含义是否正确取决于题目怎么说，如果要求正好填满背包，那么这就是对的。
⑼ 0-1背包问题用什么实现算法最好
我们书上给的0-1背包问题是是用动态规划方法做的这个算法是动态规划的典型应用所以你把动态规划的思想搞清楚就应该可以理解了下面我把动态规划的思想给你说一下,希望对你有所帮助.哦..不好意思..时间不多了..你自己到网上找一下这方面的思想..然后结合一个实例认真研读一下..弄懂之后..你对动态规划..0-1背包问题就会有比较深入的理解.建议好好学一下算法..这对计算机专业学生来说很重要..我越来越觉得祝学有所成