0-1背包问题的动态规划法与回溯法

0-1背包问题的动态规划法与回溯法一、动态规划状态转移方程:算法:例子:例:0-1背包问题。在使用动态规划算法求解0-1背包问题时,使用二维数组m[i][j]存储背包剩余容量为j,可选物品为i、i+1、……、n时0-1背包问题

大家好,又见面了,我是你们的朋友全栈君。

一、动态规划

状态转移方程:

 1 从前往后:
 2 if(j>=w[i])
 3     m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
 4 else
 5     m[i][j]=m[i-1][j];
 6  
 7 从后往前:
 8 if(j>=w[i])
 9     m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
10 else
11     m[i][j]=m[i+1][j];

算法:

 1 从前往后:
 2 for(int i=1;i<=n;i++)
 3     for(int j=1;j<=c;j++)
 4     {
 5         if(j>=w[i])
 6         {
 7             m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
 8         }
 9         else//这里没有考虑j<0的情况,因为算法中j取不到
10         {
11             m[i][j]=m[i-1][j];
12         }
13     }
14  
15 从后往前:
16 for(int i=n;i>=1;i--)
17     for(int j=1;j<=c;j++)
18     {
19         if(j>=w[i])
20         {
21             m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
22         }
23         else
24         {
25             m[i][j]=m[i+1][j];
26         }
27     }

例子:

例:0-1背包问题。在使用动态规划算法求解0-1背包问题时,使用二维数组m[i][j]存储背包剩余容量为j,可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制

重量数组w = {4, 6, 2, 2, 5, 1},

价值数组v = {8, 10, 6, 3, 7, 2},

背包容量C = 12时对应的m[i][j]数组。(从前往后)

<span role="heading" aria-level="2">0-1背包问题的动态规划法与回溯法

例题代码 :

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 #define N 20
 5 using namespace std;
 6 int main()
 7 {
 8     int w[N]={0,4,6,2,2,5,1},v[N]={0,8,10,6,3,7,2};
 9     int m[N][N];
10     memset(m,0,sizeof(m));
11     int n=6,c=12;   //n,c均要小于N 
12     for(int i=1;i<=n;i++)
13     for(int j=1;j<=c;j++)
14     {
15         if(j>=w[i])
16         {
17             m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
18         }
19         else
20         {
21             m[i][j]=m[i-1][j];
22         }
23     }
24     cout<<m[n][c]<<endl; //从前往后
25  
26     /*
27     for(int i=n;i>=1;i--)
28     for(int j=1;j<=c;j++)
29     {
30         if(j>=w[i])
31         {
32             m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
33         }
34         else
35         {
36             m[i][j]=m[i+1][j];
37         }
38     }
39     cout<<m[1][c]<<endl;//从后往前
40     */
41     return 0;
42 }

二、回溯法

 1进入左子树条件:cw+w[i]<=c   //cw为当前重量

 2进入右子树条件(减枝函数):cp+r>bestp   //cp为当前价值,bestp为当前最优价值,r为当前剩余物品价值总和。cp+r由函数     Bound计算。

 3需要先将物品按单位重量价值从大到小排序,按序进入左子树;进入右子树时,由函数Bound计算当前节点上界,只有其上界大于当前最优价值bestp时,才进入右子树,否则减去。

算法:

 1 void Backtrack(int i)
 2 {
 3     if(i>n)  //到达叶节点
 4     {
 5         bestp=cp; 
 6         return;
 7     }
 8     if(cw+w[i]<=c)  //进入左子树
 9     {
10         cw+=w[i];
11         cp+=v[i];
12         Backtrack(i+1);
13         cw-=w[i];
14         cp-=v[i];
15     }
16     if(Bound(i+1)>bestp)  //进入右子树
17     {
18         Backtrack(i+1);
19     }
20 } 
21  
22 int Bound(int i)  //计算上界
23 {
24     int cleft=c-cw;
25     int b=cp;          
26     while(i<=n&&w[i]<=cleft)  //以物品单位重量价值递减序装入物品
27     {
28         cleft-=w[i];
29         b+=v[i];
30         i++;
31     }
32     if(i<=n)//装满背包
33     {
34         b+=v[i]*(cleft/w[i]);
35     }
36     return b;
37 }

例子代码:

 1 #include<iostream>
 2 #define N 20
 3 using namespace std;
 4 int w[N]={0,4,6,2,2,5,1},v[N]={0,8,10,6,3,7,2};
 5 int n=6,c=12;
 6 int cp=0,cw=0,bestp=0;
 7 int Bound(int i)  //计算上界
 8 {
 9     int cleft=c-cw;
10     int b=cp;          
11     while(i<=n&&w[i]<=cleft)  //以物品单位重量价值递减序装入物品
12     {
13         cleft-=w[i];
14         b+=v[i];
15         i++;
16     }
17     if(i<=n)//装满背包
18     {
19         b+=v[i]*(cleft/w[i]);
20     }
21     return b;
22 }
23 void Backtrack(int i)
24 {
25     if(i>n)  //到达叶节点 
26     {
27         bestp=cp; 
28         return;
29     }
30     if(cw+w[i]<=c)  //进入左子树
31     {
32         cw+=w[i];
33         cp+=v[i];
34         Backtrack(i+1);
35         cw-=w[i];
36         cp-=v[i];
37     }
38     if(Bound(i+1)>bestp)  //进入右子树 
39     {
40         Backtrack(i+1);
41     }
42 } 
43  
44 int main()
45 {
46     Backtrack(1);
47     cout<<bestp<<endl;
48     return 0;
49 }

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/155389.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • Tensorflow2实现像素归一化与频谱归一化[通俗易懂]

    Tensorflow2实现像素归一化与频谱归一化[通俗易懂]归一化技术的改进是生成对抗网络(GenerativeAdversarialNetworks,GAN)中众多改进的一种,本文介绍常用于当前GAN中的像素归一化(Pixelnormalization,或称为像素规范化)和频谱归一化(Spectralnormalization,或称频谱规范化),在高清图片生成中,这两种归一化技术得到了广泛使用,最后使用Tensorflow2实现像素归一化和频谱归一化。

    2022年8月31日
    7
  • 简述最优二叉树(赫夫曼树)[通俗易懂]

    简述最优二叉树(赫夫曼树)[通俗易懂]什么是哈夫曼树:给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。哈夫曼树被用来进行哈夫曼编码,下面来介绍哈夫曼编码:假设需要传送的电文为“ABACCDA”,它只有四种字符,只需要用两个字符的串就可以分辨,假设A,B,C,D的编码分别是00,01,10,11,则该电文的编码便是:“00010010101100”,总长为14位,对方接收时,只需要二位一

    2025年8月1日
    3
  • qq打不开显示0xc0000005_0xc0000001怎么解决

    qq打不开显示0xc0000005_0xc0000001怎么解决  电脑出现网络不畅的问题很让人头疼,今天尝试了好几种方法,最终终于解决,特此进行记录。1.命令行重置单击“开始”,在开始搜索框中键入cmd,右键单击“cmd.exe”,单击“以管理员身份运行”。输入netshwinsockreset。重启电脑。  重启电脑以后问题依然存在,根据调研发现可能是注册表的问题。2.修复注册表2.1修复方法一退出所有活动的桌面任务(避免注…

    2022年10月8日
    4
  • 《项目经理演讲与呈现技巧》总结

    《项目经理演讲与呈现技巧》总结

    2021年9月13日
    57
  • 递归迭代动态规划「建议收藏」

    递归迭代动态规划「建议收藏」一、定义递归:程序调用自身,从顶部将问题分解,其问题与其子问题是同一概念。通过解决掉所有分解出来的小问题,来解决整个问题。迭代:利用变量的原值推算出变量的下一个值。递归中一定有迭代,但是迭代中不一定有递归。动态规划:通常与递归相反,其从底部开始解决问题。将所有小问题解决掉,进而解决的整个问题。为了节约重复求相同子问题的时间,引入一个数组,把所有子问题的解存于该数组中,动态规划算法是空间换时间的算法。动态规划可以递归地实现,也可以非递归(循环的方法)地实现。运行速度:动态规划>迭代&gt

    2025年7月1日
    5
  • java递归和迭代的区别

    java递归和迭代的区别出现栈的溢出.而迭代不会!  递归的基本概念:程序调用自身的编程技巧称为递归,是函数自己调用自己.一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合.使用递归要注意的有两点:1)递归就是在过程或函数里面调用自身;2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口. 递归分为两个阶段:1)递推:把复杂的问题的求解推到比原问

    2022年5月5日
    49

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号