设所给0-1背包问题的子问题

的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式:

注:(3.4.3)式此时背包容量为j，可选择物品为i。此时在对xi作出决策之后,问题处于两种状态之一:

(1)背包剩余容量是j,没产生任何效益； (2)剩余容量j-wi,效益值增长了vi ；

1.3算法描述

int m[100][100];//前i个物品装入容量为j的背包中获得的最大价值 int s;//获得的最大价值 int w[15];//物品的重量 int v[15];//物品的价值

int x[15];//物品的选取状态，1表示被选中 0表示未选中 int n,i;

int c;//背包最大容量

int max(int a,int b)//获得最大值 int min(int a,int b)//获得最小值

void KnapSack(int n,int w[],int v[],int c)//背包问题主算法

先为m[n][j] 初始化初值然后根据递归方程式进行穷举递归直到 m[1][c]， m[1][c] 即为所获得的最大价值。

void Traceback(int n,int w[],int x[],int c)//回溯算法，依次标注被选中的物品

通过一个循环过程检验装入第i个物品与装入i+1个物品的价值如果相同，则x[i]=0。

1.4程序实现及程序截图 1.4.1程序源码

#include using namespace std;

int m[100][100];//前i个物品装入容量为j的背包中获得的最大价值 int max(int a,int b)

4 {

if(a>=b) return a; else return b; }

int min(int a,int b) {

if(a>=b) return b; else return a; }

void KnapSack(int n,int w[],int v[],int c) { int i,j;

int jMax=min(w[n]-1,c); for(j=0;j<=jMax;j++) m[n][j]=0; for(j=w[n];j<=c;j++) m[n][j]=v[n]; for(i=n-1;i>1;i--) {

jMax=min(w[i]-1,c);

for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(j=w[i];j

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); }

m[1][c]=m[2][c]; if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); }

void Traceback(int n,int w[],int x[],int c) { int i;

for(i=1;i

if(m[i][c]==m[i+1][c]) x[i]=0; else{x[i]=1;c-=w[i];} x[n]=(m[n][c])?1:0; } int main()

1.4.2程序截图

{

int s;//获得的最大价值 int w[15];//物品的重量 int v[15];//物品的价值 int x[15];//物品的选取状态 int n,i;

int c;//背包最大容量

cout <<\请输入背包的最大容量:\ cin>>c;

cout<<\输入物品数:\\n\ cin>>n;

cout<<\请分别输入物品的重量:\ for(i=1;i<=n;i++) cin>>w[i];

cout<<\请分别输入物品的价值:\ for(i=1;i<=n;i++) cin>>v[i];

KnapSack(n,w,v,c); Traceback(n,w,x,c); s=m[1][c];

cout<<\最大物品价值为:\ cout<

cout<<\选中的物品为：\ for(i=1;i<=n;i++) cout<

return 0;

｝

5

1.5学习或程序调试心得

利用动态规划求解0-1背包问题的复杂度为0(min{nc,2n}。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题。

6

作业2 0-1背包问题的回溯算法

1.1算法应用背景

背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。

那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题给出具体算法设计和实现过程。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。

2.2算法原理 2.2.1 问题描述

问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品莺量为wi，价值为pi，假定物品i的一部分xi(0?xi?1)放人背包，获得价值为xipi，由于背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。

背包问题的数学描述如下：要求找到一个n元向量(x1，x2…xn)，在满足约束条件：

???xiwi?M情况下，使得目标函数max?xi??0?x?1i?p，其中，1?i?n；M>0；wi>0；pi>0。

i满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优

解。

给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。

0-1背包问题的符号化表示是，给定M>0， w i >0， pi >0，1?i?n ，要求找到一个n元0-1向量向量(x1，x2…xn)， X i =0 或1 , 1?i?n, 使得

?xwii?M ，而且?xip达到最大。

i2.2.2算法分析

1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应

7