作业帮 > 数学 > 作业

算法分析与设计题目 请求解0/1/2背包问题：有1个背包、其容量为C,有n种物品（每个物品种类i都自己的重量wi和价值v

来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/07/09 02:08:09
算法分析与设计题目
请求解0/1/2背包问题：有1个背包、其容量为C,有n种物品（每个物品种类i都自己的重量wi和价值vi）,找出一个最优装包方案,使得包内物品总价值最大（约束：物品种类i只能不装或装1个或装2个到背包内）.定义该问题的最优值函数为m( i,j )：表示剩余容量为j,剩余物品种类为i,i+1,…,n时最优装包方案的物品总价值.
1）请给出m ( i,j ) 的递归计算公式
2）请给出0/1/2背包问题的动态规划算法.
3）对0/1/2背包问题的实例w=[3,2,1,4,5],v=[25,20,15,40,50],C=6用动态规划算法求解.
(1)  m(i,j)=max( m(i-1,j-w[i])+v[i] , m(i-1,j) , m(i-1,j-2*w[i])+2*v[i] );
(2)  for (int i=0;i<=n;i++)
    for (int j=0;j<=c;j++) m[i][j]=-10000;
m[0][0]=0;
for (int i=1;i<=n;i++)
    for (int j=0;j<=c;j++)
    {
        m[i][j]=max(m[i][j],m[i-1][j]);
        if (j+w[i]<=c) m[i][j+w[i]]=max(m[i][j+w[i]],m[i-1][j]+v[i]);
        if (j+2*w[i]<=c) m[i][j+2*w[i]]=max(m[i][j+2*w[i]]+2*v[i]);
    }(3)
取 2个 第二种物品,2个 第三种物品,获得价值最大为70
算法分析与设计题目 请求解0/1/2背包问题：有1个背包、其容量为C,有n种物品（每个物品种类i都自己的重量wi和价值v 分布估计算法求解0-1背包问题算法的C语言程序； 01背包问题的贪心K阶优化算法设计(物品不可拆分） C语言算法求助：假设有这么一组物品,其大小和价值如下表所示：物品编号\x05大小\x05价值1\x05 2\x0532\ 分别用贪心算法和动态规算法求解0/1背包问题的最优解和最大收益 贪心算法背包问题设有n=8个体积分别为54,45,43,29,23,21,14,1的物体和一个容积为C=110的背包,问 pascal 0/1背包和完全背包的差别? 用贪心算法求解背包问题的最优解. 0-1背包问题的测试数据 英语单词：satchel 和 bag 都有 背包 的意思 其具体区别是什么 C语言 贪心算法求背包问题 C语言背包问题递归算法