动态规划背包问题（例题）

编程汇总 • 2025-01-19 23:27 • 阅读 8

物品编号 1 2 3 4
物品体积 2 3 4 5
物品价值 3 4 5 6
求容积为8的背包能装的最大价值为多少？

解题思路
动态规划解题步骤
1）确定状态
注意：动态规划一般要开数组，首先要明确数组的每个元素所代表的意义。
确定状态需要两个意识：（1）最后一步（2）子问题。
2）转移方程的确定
3）初始化条件和边界情况
注意：初始状态大部分都是为零，用转移方程算不出来的才需要手动定义状态。
4）计算顺序
注意：一般的计算顺序是从小到大，从上到下从左到右（二维）。

本题的状态转移方程很容易就可以得出来是f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i])
这里有两个方面需要考虑，第一个是你准备将第i件物品放入，第二是你不准备放入。所以你首先需要比较体积大小，然后比较物品价值。f[i-1][j]是你没有放入物品时的情况，f[i-1][j-vol[i]]+val[i]是你要放入物品时，计算当前物品和剩余空间价值的和。然后求他们的最大值max。

本题还提供了back（）,是求解到底去了哪几件物品，是背包问题的回溯。

#include

#include

#include

#include

#include

#include

using namespace std;

int val[]={ 

   0,3,4,5,6};

int vol[]={ 

   0,2,3,4,5};

int f[5][9];

bool flag[5]={ 

   true};

//背包的容积为8

//物品编号1,2,3,4

//物品容积2,3,4,5

//物品体积3,4,5,6 



int maxvalue(){ 

   

for(int i=0; i<=4; i++){ 

   
	for(int j=0; j<=8; j++){ 

   
		if(i==0 || j==0){ 

   
			f[i][j]=0; 
		}else{ 

   
			if(vol[i]<=j)
				f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i]);
			else{ 

   
				f[i][j]=f[i-1][j];
			}
		}
	}
}


} 



int back(int i, int j){ 

   
if(i==0){ 

   
	for(int i=1; i<5; i++){ 

   
		if(flag[i]) cout<	}
}
if(f[i][j]==f[i-1][j]){ 

   
	back(i-1,j);
}
else if(f[i][j]==f[i-1][j-vol[i]]+val[i]){ 

   
	flag[i]=true;
	back(i-1,j-vol[i]);
}

}



int main(){ 

   
maxvalue();
for(int i=0; i<=4; i++){ 

   
	for(int j=0; j<=8; j++){ 

   
		printf("%4d",f[i][j]);
	}
	cout<}

back(4,8);
return 0;

}

动态规划背包问题（例题）

相关推荐