C++动态规划01背包

2021-01-20 02:12

阅读：759

标签：结果递推 amp 组合 nbsp oid for 变量 htm

动态规划01背包实现：

借鉴的这篇博文：

https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

题目：在背包容量为8的情况下，根据下图的数据动态规划得到最优解，实现右图所示的程序代码

技术图片

最重要的就是寻找递推关系式：

定义V[i,j]:当背包容量为j时，前i个物品最佳组合对应的值。

递推关系：

（1）当背包的容量不允许装入第i件物品时，和前一个物品装入背包一样。即：V[i][j]=V[i-1][j]

（2）当背包的容积可以装入第i件物品时，分两种情况，A装入第i件物品不是最优，还不如不装。B装入第i件物品是最优。即:V[i][j]=max(V[i-1][j],V[i][j-w[i]]+v[i])

代码实现：

#include
 using namespace std;
 int w[5]={0,2,3,4,5};
 int v[5]={0,3,4,5,6};
 int V[5][9]; 
 int c=8;
 int B()
 {
 	int i,j;
 	for(i=0;i

　下面是带上回溯找出解的组成的代码：

 #include
 using namespace std;
 int w[5]={0,2,3,4,5};
 int v[5]={0,3,4,5,6};
 int V[5][9]; 
 int c=8;
 int item[4];
 int B()
 {
 	int i,j;
 	for(i=0;i=0)
    {
        if(V[i][j]==V[i-1][j])//相等说明没装
        {
            item[i]=0;//全局变量，标记未被选中
            FindWhat(i-1,j);
        }
        else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] )
        {
            item[i]=1;//标记已被选中
            FindWhat(i-1,j-w[i]);//回到装包之前的位置
        }
    }
}

int main(){
B();
//显示填好的表格 
cout

贴上结果便于理解：

技术图片

时间复杂度：

O(物体个数*背包容积)=O(number*capacity)

空间复杂度：

用二维表实现的，所以和时间复杂度一样。

O(物体个数*背包容积)=O(number*capacity)

C++动态规划01背包

标签：结果递推 amp 组合 nbsp oid for 变量 htm

原文地址：https://www.cnblogs.com/zhaoxiansheng666/p/12905475.html

上一篇：SpringBoot连接Redis-sentinel模式

下一篇：JavaScript中的同步与异步

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：C++动态规划01背包
文章链接：http://soscw.com/index.php/essay/44327.html

亲，登录后才可以留言！

C++动态规划01背包

评论

热门文章

推荐文章

最新文章

置顶文章