0/1背包问题

动态规划问题

背包问题是一个典型的动态规划问题，动态规划就是利用分治思想和解决冗余的办法来处理问题，采用dp数组来实现记忆搜索，从而解决冗余，而分治思想就是递归的思想，总的问题可以分为若干相同的子问题，所有子问题的解合并即是该问题的解。
动态规划是全面处理最优问题，时间和空间复杂度比较大，但是可以优化，这是一个覆盖全部子问题的解决方法，重点是全面和最优

问题描述

有一个背包，容量是10，有以下4样物品可供选择装在背包中（每样物品只能装一个），求在容量限制范围内装得的最高价值。

递推关系

V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

代码实现

#include <iostream>
using namespace std;

int main(){
	
	int a[4][2] = {{2,3}, {3,4}, {5,6}, {6,8}};			//存放物品容量和价值的数组 
	int b[5][11];										//用于动态规划的数组
	
	int i, j;
	int curValue;
	
	for (i=0; i<5; i++) {
		
		for (j=0; j<11; j++) {
			
			if (i==0) {									//不装任何编号的物品，当然最大价值也为0 
				b[i][j] = 0;
			}
			
			else{
				
				if (a[i-1][0]>j) {						//装不下当前编号的东西 
					b[i][j]=b[i-1][j];					//包括当前编号（i以内）的最大价值与不包括当前编号(只包括i-1以内)的最大价值相同 
				}
				
				else{									//装的下当前编号的东西 
				
					curValue = a[i-1][1] + b[i-1][j- a[i-1][0] ];		//当前最大价值（可能性1） = 包括当前编号物品的价值 + 去除当前编号容量后的最大价值 
					
					if (curValue>b[i-1][j]) {							//如果可能性1>不包括当前编号的最大价值（可能性2） 
						b[i][j] = curValue;								//当前最大价值 取可能性1与可能性2的最大值（可能性1） 
					}
					else {												//如果可能性1<不包括当前编号的最大价值（可能性2）
						b[i][j] = b[i-1][j];							//当前最大价值 取可能性1与可能性2的最大值（可能性2） 
					}
					
				} 
			
			}
			
			
			cout << b[i][j] << "t";									//输出最大价值矩阵 
			
		}
		
		cout << endl;
	} 
	
	return 0;
}

求最大价值物品编号集合

问题描述

运用回溯法，求得取得最大价值的物品编号集合

代码实现

#include <iostream>
using namespace std;

int main(){
	
	int a[4][2] = {{2,3}, {3,4}, {5,6}, {6,8}};			//存放物品容量和价值的数组 
	int b[5][11];										//用于动态规划的数组
	
	int i, j;
	int curValue;
	
	for (i=0; i<5; i++) {
		
		for (j=0; j<11; j++) {
			
			if (i==0) {									//不装任何编号的物品，当然最大价值也为0 
				b[i][j] = 0;
			}
			
			else{
				
				if (a[i-1][0]>j) {						//装不下当前编号的东西 
					b[i][j]=b[i-1][j];					//包括当前编号（i以内）的最大价值与不包括当前编号(只包括i-1以内)的最大价值相同 
				}
				
				else{									//装的下当前编号的东西 
				
					curValue = a[i-1][1] + b[i-1][j- a[i-1][0] ];		//当前最大价值（可能性1） = 包括当前编号物品的价值 + 去除当前编号容量后的最大价值 
					
					if (curValue>b[i-1][j]) {							//如果可能性1>不包括当前编号的最大价值（可能性2） 
						b[i][j] = curValue;								//当前最大价值 取可能性1与可能性2的最大值（可能性1） 
					}
					else {												//如果可能性1<不包括当前编号的最大价值（可能性2）
						b[i][j] = b[i-1][j];							//当前最大价值 取可能性1与可能性2的最大值（可能性2） 
					}
					
				} 
			
			}
			
			
			cout << b[i][j] << "t";									//输出最大价值矩阵 	
		}	
		cout << endl;
	}
	
	cout << "最大价值为：" << b[4][10] <<endl;
	
	

	//运用回溯法，求解最大价值物品编号集合
	i=4;
	j=10;

	while (j>0) {														//当容量>0时，持续回溯
	
		if (b[i][j]==b[i-1][j]) {			//如果包含编号（i以内）的最大价值与不包含（i-1以内）一致
			i--;							//说明该编号未在最大价值编号集合中，i自减
		}
		
		else {
			cout << "编号" << i << "在最大价值集合中" << endl;
			j -= a[i-1][0];					//否则，减去该编号的容量
			i--;
		}
	}
	
	return 0;
}

程序的输出结果

0 0 0 0 0 0 0 0 0 0 0
0 0 3 3 3 3 3 3 3 3 3
0 0 3 4 4 7 7 7 7 7 7
0 0 3 4 4 7 7 9 10 10 13
0 0 3 4 4 7 8 9 11 12 13
最大价值为：13
编号3在最大价值集合中
编号2在最大价值集合中
编号1在最大价值集合中

背包问题也是非常有意思的动态规划问题！

完全背包问题

问题描述

有一个背包，容量是20，有以下4样物品可供选择（每样物品可以装无限个），求在容量限制范围内装得的最高价值。

递推关系

V(i,j)=max｛ V(i-1,j)，V(i,j-w(i))+v(i) ｝

代码实现

最后

以上就是辛勤钢铁侠为你收集整理的背包问题的C++实现（动态规划与回溯法）0/1背包问题完全背包问题的全部内容，希望文章能够帮你解决背包问题的C++实现（动态规划与回溯法）0/1背包问题完全背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。