0-1背包问题“动态规划”——《算法设计与分析(第五版)》

2022-08-23 10:58:18

一、算法要求

给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

1. 思路

有n种可选物品1,…,n ,放入容量为c的背包内,使装入的物品具有最大效益。

n :物品个数
c :背包容量
p1,p2, …, pn:个体物品效益值
w1,w2, …,wn:个体物品容量

0-1背包问题的解法:物品1,…,n的一种放法(x1, ···,xn的0/1赋值),使得效益值最大。
假定背包容量不足以装入所有物品:面临选择

优化原理:无论优化解是否放物品1,优化解对物品2,…,n的放法,相对剩余背包容量,也是优化解。

2. 示例

假设:n=5,c=10
      p=[6,3,5,4,6]
      w=[2,2,6,5,4]

在这里插入图片描述
(1,1,0,0,1)为其优化解,即放物品1,2,5 。物品1占背包容量2,剩下容量为8。

考虑子问题:n=4,c=8,物品为2,3,4,5
(1,0,0,1),即放物品2和5,是子问题的优化解,背包问题满足优化原理。


二、完整代码

1. 主文件

main.cpp:

#include"Improve1.h"intmain(){//初始化控制台Console();//核心算法CoreAlgorithm();// 输出
	cout<<"\nThe maximum total value of the items in the backpack is:"<< m[1][capacityPack]<< endl;

	cout<<"The selected item situation is:";for(int i=1; i<= numItem; i++)
		cout<< x[i]<<" ";

	cout<< endl;return0;}

2. 头文件

Improve1.h:

#pragmaonce#ifndef__IMPROVE1__#define__IMPROVE1__#include<iostream>#include<iomanip>#include<cstdio>#include<algorithm>
using namespace std;/*n :物品个数
 *c :背包容量
 *p1,p2, …, pn:个体物品效益值
 *w1,w2, …,wn:个体物品容量*/int numItem=5,
	capacityPack=10;int weightItem[]={0,2,2,6,5,4},//从第一序列开始
	valueItem[]={0,6,3,5,4,6};int* x;// 物品是否被放入背包int** m;// 最大价值// 用户输入voidConsole(){

	cout<<"The following are the default items’ quantity, value and weight and backpack capacity: \n"<<"\n#Number of items: "<< numItem<<"\n#Number of backpacks: "<< capacityPack;

	cout<<"\n#Corresponding weight: ";for(int i=1; i< numItem+1; i++)
		cout<<setw(3)<< weightItem[i];

	cout<<"\n#Corresponding value: ";for(int i=1; i< numItem+1; i++)
		cout<<setw(3)<< valueItem[i];

	x= newint[numItem+1];
	m= newint*[numItem+1];for(int i=0; i<= numItem; i++){
		m[i]= newint[capacityPack+1];memset(m[i],0,sizeof(int)*(capacityPack+1));// 将表m所有元素设为0}
	cout<< endl;}//核心算法voidCoreAlgorithm(){//Knapsack最大价值表int jMax=min(weightItem[numItem]-1, capacityPack);// 避免存在单个重量超出背包容量的物品使数组m越界for(int j=0; j<= jMax; j++)// 以下两个for循环是最大价值表m的最后一行
		m[numItem][j]=0;for(int j= weightItem[numItem]; j<= capacityPack; j++)
		m[numItem][j]= valueItem[numItem];for(int i= numItem-1; i>1; i--){// 以下是表m最后一行以上的部分
		jMax=min(weightItem[i]-1, capacityPack);for(int j=0; j<= jMax; j++)// 背包容量<物品重量,即装不下;将m[i+1][j](下一行同列)的值赋给m[i][j]
			m[i][j]= m[i+1][j];for(int j= weightItem[i]; j<= capacityPack; j++)// 背包容量>=物品重量,即可以装下;//		放:m[i][j]=m[i + 1][j - w[i]] + v[i]//		不放:m[i][j]=m[i + 1][j]// 哪个价值大,就采取哪种方式
			m[i][j]=max(m[i+1][j], m[i+1][j- weightItem[i]]+ valueItem[i]);}
	m[1][capacityPack]= m[2][capacityPack];if(capacityPack>= weightItem[1])
		m[1][capacityPack]=max(m[1][capacityPack], m[2][capacityPack- weightItem[1]]+ valueItem[1]);//Traceback将最优解存入数组int cTemp= capacityPack;// 临时背包容量for(int i=1; i< numItem; i++){if(m[i][cTemp]== m[i+1][cTemp])
			x[i]=0;// 价值相等,说明没有放入这个物品,0else{
			x[i]=1;// 价值不相等,说明放入了这个物品,1
			cTemp-= weightItem[i];// 放入了一个物品,背包剩余容量为原容量-物品重量}}
	x[numItem]=(m[numItem][capacityPack])?1:0;// 最后一个物品,非0为true放入,0为false不放入}#endif

3. 效果展示

在这里插入图片描述


三、补充

优化值间的递归式:
虽然不知道优化解是否放物品1,但从优化原理能建立优化值间的递归式:
设f(i, y)为以背包容量y,放物品i,…,n,得到的优化效益值,以下递归关系成立:

f(1,c)=max{f(2,c), f(2,c-w1)+p1}  不放物品1、放物品1
先求子问题的优化值(递归),再从2种可能性中求出最优的。

须对任意给定容量y,任意i,…,n 种物品求解子问题。

举例:

n=3, c=116       
w=[100,14,10]
p=[20,18,15]
放进物品1(x1 = 1),背包容量还剩r=16, [x2,x3]= [1,0] 为子问题的优化解,值为18,总效益值为20+18=38
不放物品1(x1= 0)则对于剩下的两种物品而言,容量限制条件为116,[1,1]为子问题优化解,值为33。
前者效益值为38,后者为33; 
所以优化解为[1,1,0], 优化值为max{38,33}=38。
  1. 算法复杂度分析:
    (1)时间复杂度:算法中有主要的是两层嵌套的for循环,其时间复杂度为O(n×w)。
    (2)空间复杂度:由于二维数组c[n][w],所以空间复杂度为O(n×w)。
  2. 算法优化拓展:
    首先有一个主循环i=1,2,…,N,每次算出来二维数组c[i][0~w]的所有值。那么,如果只用一个数组 dp[0~w],能不能保证第i次循环结束后dp[i]中表示的就是我们定义的状态 c[i][j]呢?
    c[i]]由c[i-1][i]和c[i-1] [j-w[i]]两个子问题递推而来,能否保证在递推 c[i][i]时(也即在第i次主循环中递推 dp[j]时)能够得到c[i-1][j]和c[i-1][j-w[i]]的值呢﹖事实上,这要求在每次主循环中以j=w,w-1,…,1,0的顺序倒推dp[j],这样才能保证递推 dp[j]时dp[j-c[i]]保存的是状态c[i-1][j-w[i]]的值。

伪代码如下:

for i=1..nfor j=w..0
		dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
其中,dp[j]=max {dp[j],dp[j-w[i]]}就相当于转移方程c[i][j]-max {c[i-1][j],c[i-1][j-w[i]]},
因为这里的dp[j-w[i]]	就相当于原来的c[i-1][j-w[i]]。

文档供本人学习笔记使用,仅供参考。

  • 作者:NI'CE'XIAN
  • 原文链接:https://blog.csdn.net/m0_46895048/article/details/122506153
    更新时间:2022-08-23 10:58:18