下载文档原格式
回溯法解决0-1背包问题问题描述： 有n件物品和⼀个容量为c的背包。
第i件物品的价值是v[i]，重量是w[i]。
求解将哪些物品装⼊背包可使价值总和最⼤。
所谓01背包，表⽰每⼀个物品只有⼀个，要么装⼊，要么不装⼊。
回溯法： 01背包属于找最优解问题，⽤回溯法需要构造解的⼦集树。
在搜索状态空间树时，只要左⼦节点是可⼀个可⾏结点，搜索就进⼊其左⼦树。
对于右⼦树时，先计算上界函数，以判断是否将其减去，剪枝啦啦！上界函数bound():当前价值cw+剩余容量可容纳的最⼤价值<=当前最优价值bestp。
为了更好地计算和运⽤上界函数剪枝，选择先将物品按照其单位重量价值从⼤到⼩排序，此后就按照顺序考虑各个物品。
#include <stdio.h>#include <conio.h>int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装⼊//按单位价值排序void knapsack(){int i,j;int temporder = 0;double temp = 0.0;for(i=1;i<=n;i++)perp[i]=v[i]/w[i];for(i=1;i<=n-1;i++){for(j=i+1;j<=n;j++)if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]{temp = perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i];order[i]=order[j];order[j]=temporder;temp = v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数void backtrack(int i){double bound(int i);if(i>n){bestp = cp;return;}if(cw+w[i]<=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)>bestp)//符合条件搜索右⼦数backtrack(i+1);}//计算上界函数double bound(int i){double leftw= c-cw;double b = cp;while(i<=n&&w[i]<=leftw){leftw-=w[i];b+=v[i];i++;}if(i<=n)b+=v[i]/w[i]*leftw;return b;}int main(){int i;printf("请输⼊物品的数量和容量：");scanf("%d %lf",&n,&c);printf("请输⼊物品的重量和价值：");for(i=1;i<=n;i++){printf("第%d个物品的重量：",i);scanf("%lf",&w[i]);printf("价值是：");scanf("%lf",&v[i]);order[i]=i;}knapsack();backtrack(1);printf("最有价值为：%lf\n",bestp);printf("需要装⼊的物品编号是：");for(i=1;i<=n;i++){if(put[i]==1)printf("%d ",order[i]);}return 0;}时间复杂度分析： 上界函数bound()需要O(n)时间，在最坏的情况下有O(2^n)个右⼦结点需要计算上界，回溯算法backtrack需要的计算时间为O(n2^n)。
一、 问题描述0/1背包问题:现有n 种物品，对1<=i<=n ，已知第i 种物品的重量为正整数W i ，价值为正整数V i ，背包能承受的最大载重量为正整数W ，现要求找出这n 种物品的一个子集，使得子集中物品的总重量不超过W 且总价值尽量大。
（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）二、 算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：)2(max )1()1}(1,0{11∑∑==⎪⎩⎪⎨⎧≤≤∈≤ni i i ini i i x v n i x Wx w 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量),......,,,(321n x x x x X =。
首先说明一下0-1背包问题拥有最优解。
假设),......,,,(321n x x x x 是所给的问题的一个最优解，则),......,,(32n x x x 是下面问题的一个最优解：∑∑==⎪⎩⎪⎨⎧≤≤∈-≤ni i i ini i i x v n i x x w W x w 2211max )2}(1,0{。
如果不是的话，设),......,,(32n y y y 是这个问题的一个最优解，则∑∑==>n i ni ii ii xv y v 22，且∑=≤+ni iiW yw x w 211。
因此，∑∑∑====+>+ni i i n i n i i i i i x v x v x v y v x v 1221111，这说明),........,,,(321n y y y x 是所给的0-1背包问题比),........,,,(321n x x x x 更优的解，从而与假设矛盾。
穷举法：用穷举法解决0-1背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。
分⽀界限法0-1背包问题（优先队列式分⽀限界法）输⼊要求有多组数据。
每组数据包含2部分。
第⼀部分包含两个整数C （1 <= C <= 10000）和 n （1 <= n <= 10，分别表⽰背包的容量和物品的个数。
第⼆部分由n⾏数据，每⾏包括2个整数 wi（0< wi <= 100）和 vi（0 < vi <= 100），分别表⽰第i个物品的总量和价值输出要求对于每组输⼊数据，按出队次序输出每个结点的信息，包括所在层数，编号，背包中物品重量和价值。
每个结点的信息占⼀⾏，如果是叶⼦结点且其所代表的背包中物品价值⼤于当前最优值（初始为0），则输出当前最优值 bestv 和最优解bestx（另占⼀⾏）参见样例输出测试数据输⼊⽰例5 32 23 22 3输出⽰例1 1 0 02 2 2 23 5 2 24 10 4 5bestv=5, bestx=[ 1 0 1 ]4 11 2 23 4 5 42 3 0 0⼩贴⼠可采⽤如下的结构体存储结点：typedef struct{int no; // 结点在堆中的标号int sw; // 背包中物品的重量int sv; // 背包中物品的价值double prior; // 优先值 sv/sw}Node;#include<stdio.h>#include<math.h>#include<string.h>typedef struct {int no; // 结点标号int id; // 节点idint sw; // 背包中物品的重量int sv; // 背包中物品的价值double prior; // sv/sw}Node;int surplusValue(int *v,int n,int y) {int sum = 0;for(int i = y; i <= n; i++) {sum += v[i];}return sum;}void qsort(Node *que,int l,int r) {int len = r - l + 1;int flag;for(int i = 0; i < len; i ++) {flag = 0;for(int j = l; j < l + len - i; j++) {if(que[j].prior < que[j+1].prior) {Node t = que[j];que[j] = que[j+1];que[j+1] = t;flag = 1;}}//if(!flag ) return;}}void branchknap(int *w,int *v,int c,int n) {int bestv = 0;int f = 0;int r = 0;Node que[3000];memset(que,0,sizeof(que));int path[15];que[0].no = 1;que[0].id = que[0].sv = que[0].sw = que[0].prior = 0;while(f <= r) {Node node = que[f];printf("%d %d %d %d\n",node.id+1,node.no,node.sw,node.sv);if(node.no >= pow(2,n)) {if(node.sv > bestv) {bestv = node.sv;printf("bestv=%d, bestx=[",bestv);int temp = node.no;int i = 0;while(temp > 1) {if(temp % 2 == 0)path[i] = 1;elsepath[i] = 0;temp /= 2;i++ ;}i--;while(i >= 0) {while(i >= 0) {printf(" %d",path[i]);i--;}printf(" ]\n");}} else {if((node.sw + w[node.id + 1]) <= c && surplusValue(v,n,node.id+1) + node.sv > bestv) { r++;que[r].id = node.id + 1;que[r].no = node.no*2;int id = node.id + 1;que[r].sv = node.sv + v[id];que[r].sw = node.sw + w[id];que[r].prior = que[r].sv / (que[r].sw*1.0);}if(surplusValue(v,n,node.id+2) + node.sv > bestv) {r++;que[r].id = node.id + 1;que[r].no = node.no*2 + 1;que[r].sv = node.sv;que[r].sw = node.sw;que[r].prior = node.prior;}}f++;qsort(que,f,r);}}int main() {int c,n;int w[15],v[15];while(~scanf("%d %d",&c,&n)){for(int i = 1; i <= n; i++) {scanf("%d %d",&w[i],&v[i]);}branchknap(w,v,c,n);}return 0;}#include<stdio.h>#include<math.h>#include<string.h>typedef int bool;#define true 1#define false 0struct Node{int no; // ?áµ?±êo?int id; //jie dian idint sw; // ±3°ü?D·µá?int sv; // ±3°ü?D·µ?µdouble prior;};struct Node queuee[2000];int w[15],v[15];int bestv = 0,c,n;int path[15]; //lu jingint surplusValue(int y) {int sum = 0;for(int i = y; i <= n; i++)sum += v[i];return sum;}void qsort(int l,int r) {// printf("------\n");int len = r - l + 1;//printf("----%d %d %d-----\n",l,r,len);bool flag;for(int i = 0; i < len ; i++) {flag = false;for(int j = l; j <l+ len -i ;j++) {if(queuee[j].prior < queuee[j+1].prior) {struct Node temp = queuee[j];queuee[j] = queuee[j+1];queuee[j+1] = temp;flag = true;}//if(!flag) return;}}// printf("---排序嘻嘻---\n");//for(int i = l; i <= r;i++ )// printf("***%d : %.2lf\n",queuee[i].no,queuee[i].prior);// printf("\n------\n");}void branchknap() {bestv = 0;int f = 0;int r = 0;queuee[0].no = 1;queuee[0].id = 0;queuee[0].sv = 0;queuee[0].sw = 0;queuee[0].prior = 0;// printf("f: %d r: %d\n",f,r);while(f <= r) {struct Node node = queuee[f];printf("%d %d %d %d\n",node.id+1,node.no,node.sw,node.sv);if(node.no >= pow(2,n)) {if(node.sv > bestv) {bestv = node.sv;//TODOprintf("bestv=%d, bestx=[",bestv);int temp = node.no;int i = 0;while(temp > 1) {if(temp%2 == 0)path[i] = 1;elsepath[i] = 0;temp /= 2;i++;}i--;while(i >= 0) {while(i >= 0) {printf(" %d",path[i]);i--;}printf(" ]\n");}} else {if((node.sw + w[node.id+1]) <= c && surplusValue(node.id+1) + node.sv > bestv) { r++;//printf("%d\n",(node.sw + w[node.id+1]));queuee[r].id = node.id+1;queuee[r].no = node.no*2;int id = node.id+1;queuee[r].sv = node.sv + v[id];queuee[r].sw = node.sw + w[id];queuee[r].prior = queuee[r].sv/(queuee[r].sw*1.0);//printf("进队id： %d\n",queuee[r].no) ;//printf("%d %d %d\n",id,v[id], w[id]);}if(surplusValue(node.id+2) + node.sv > bestv) {r++;queuee[r].id = node.id+1;queuee[r].no = node.no*2 + 1;queuee[r].sv = node.sv ;queuee[r].sw = node.sw ;queuee[r].prior = node.prior;//printf("进队id： %d\n",queuee[r].no) ;}}f++;qsort(f,r);}}int main() {while(~scanf("%d %d",&c,&n)){memset(queuee,0,sizeof(queuee));for(int i = 1; i <= n; i++) {scanf("%d %d",&w[i],&v[i]);}branchknap();}return 0;}。
0-1背包问题课程设计一、课程目标知识目标：1. 学生理解0-1背包问题的定义，掌握其数学模型及相关概念。
2. 学生掌握0-1背包问题的动态规划解法，并能够运用此方法解决相关问题。
3. 学生了解0-1背包问题在实际生活中的应用，如资源分配、行程规划等。
技能目标：1. 学生能够运用数学语言描述0-1背包问题，并建立相应的数学模型。
2. 学生通过编程实践，掌握动态规划算法在0-1背包问题中的应用。
3. 学生具备分析问题、提出解决方案并优化方案的能力。
情感态度价值观目标：1. 培养学生面对问题时的积极态度，激发学生解决问题的兴趣和热情。
2. 增强学生团队合作意识，培养沟通协调能力。
3. 使学生认识到数学建模在解决实际问题中的重要性，提高学生的应用意识。
课程性质：本课程为高中数学选修课程，结合计算机科学领域的内容，旨在培养学生的跨学科素养。
学生特点：高中生具备一定的数学基础和逻辑思维能力，对实际问题有一定的探索欲望。
教学要求：教师需引导学生从实际问题出发，通过数学建模、算法设计等环节，培养学生的分析问题和解决问题的能力。
在教学过程中，注重理论与实践相结合，关注学生的个性发展。
通过本课程的学习，使学生能够达到上述课程目标，并在实际操作中展示具体的学习成果。
二、教学内容本课程教学内容主要包括以下几部分：1. 0-1背包问题基本概念与数学模型：介绍0-1背包问题的定义、特性以及与实际生活的联系。
结合教材相关章节，让学生掌握数学建模的基本方法。
2. 动态规划原理：讲解动态规划的基本思想、原理及其在0-1背包问题中的应用。
引导学生通过实例分析，理解动态规划的优势。
3. 编程实现：结合教材内容，教授学生如何使用编程语言（如Python）实现0-1背包问题的动态规划解法。
要求学生掌握编程技巧，能够独立完成代码编写。
4. 算法优化与拓展：探讨0-1背包问题的变种及优化方法，如贪心算法、回溯算法等。
指导学生分析各种算法的优缺点，培养学生的算法优化意识。
0-1背包问题——回溯法求解【Python】回溯法求解0-1背包问题：问题：背包⼤⼩ w，物品个数 n，每个物品的重量与价值分别对应 w[i] 与 v[i]，求放⼊背包中物品的总价值最⼤。
回溯法核⼼：能进则进，进不了则换，换不了则退。
（按照条件深度优先搜索，搜到某⼀步时，发现不是最优或者达不到⽬标，则退⼀步重新选择）注：理论上，回溯法是在⼀棵树上进⾏全局搜索，但是并⾮每种情况都需要全局考虑，毕竟那样效率太低，且通过约束+限界可以减少好多不必要的搜索。
解决本问题思路：使⽤0/1序列表⽰物品的放⼊情况。
将搜索看做⼀棵⼆叉树，⼆叉树的第 i 层代表第 i 个物品，若剩余空间允许物品 i 放⼊背包，扩展左⼦树。
若不可放⼊背包，判断限界条件，若后续继续扩展有可能取得最优价值，则扩展右⼦树（即此 i 物品不放⼊，但是考虑后续的物品）。
在层数达到物品的个数时，停⽌继续扩展，开始回溯。
注：如何回溯呢？怎样得到的，怎样恢复。
放⼊背包中的重量取出，加在bagV上的价值减去。
约束条件：放⼊背包中物品的总质量⼩于等于背包容量限界条件：当前放⼊背包中物品的总价值（i及之前） + i 之后的物品总价值 < 已知的最优值这种情况下就没有必要再进⾏搜索数据结构：⽤⼀个变量记录当前放⼊背包的总价值 bagV（已扩展），⼀个变量记录后续物品的总价值 remainV（未扩展），当前已得到的⼀种最优值 bestV（全局情况），⼀个⽤0/1表⽰的数组bestArr[]记录哪些物品放⼊了背包。
核⼼结构：递归思路进⾏解决。
层层递归，递归到尽头，保留最优值，恢复递归中，层层回溯，即将原来加上去的重量与价值恢复。
# -*- coding:utf-8 -*-def Backtrack(t):global bestV, bagW, bagV,arr, bestArr, cntVif t > n: #某次深度优先搜索完成if bestV < bagV:for i in range(1, n+1):bestArr[i] = arr[i]bestV = bagVelse: #深度优先搜索未完成if bagW + listWV[t][0] <= w: #第t个物品可以放⼊到背包中，扩展左⼦树arr[t] = TruebagW += listWV[t][0]bagV += listWV[t][1]Backtrack(t+1)bagW -= listWV[t][0]bagV -= listWV[t][1]if cntV[t] + bagV > bestV: #有搜索下去的必要arr[t] = FalseBacktrack(t+1)if__name__ == '__main__':w = int(input()) #背包⼤⼩n = int(input()) #物品个数listWV = [[0,0]]listTemp = []sumW = 0sumV = 0for i in range(n):listTemp = list(map(int, input().split())) #借助临时list每次新增物品对应的list加⼊到listWV中sumW += listTemp[0]sumV += listTemp[1]listWV.append(listTemp) #依次输⼊每个物品的重量与价值bestV = 0bagW = 0bagV = 0remainV = sumVarr = [False for i in range(n+1)]bestArr = [False for i in range(n+1)]cntV = [0 for i in range(n+1)] #求得剩余物品的总价值,cnt[i]表⽰i+1~n的总价值 cntV[0] = sumVfor i in range(1, n+1):cntV[i] = cntV[i-1] - listWV[i][1]if sumW <= w:print(sumV)else:Backtrack(1)print(bestV)print(bestArr)print(cntV)检测：1052 65 34 52 43 617[False, True, False, True, False, True][24, 18, 15, 10, 6, 0]。
动态规划之-0-1背包问题及改进有N件物品和一个容量为V的背包。
第i件物品的重量是w[i]，价值是v[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
在选择装入背包的物品时，对于每种物品i，只能选择装包或不装包，不能装入多次，也不能部分装入，因此成为0-1背包问题。
形式化描述为：给定n个物品，背包容量C >0,重量第i件物品的重量w[i]>0, 价值v[i] >0 , 1≤i≤n.要求找一n元向量(X1,X2,…,X n,), X i∈{0,1}, 使得∑（w[i] * Xi）≤C,且∑ v[i] * Xi达最大.即一个特殊的整数规划问题。
数学描述为：求解最优值：设最优值m(i,j)为背包容量为j、可选择物品为i，i+1，……，n时的最优值(装入包的最大价值)。
所以原问题的解为m(1，C)将原问题分解为其子结构来求解。
要求原问题的解m(1，C)，可从m(n，C)，m(n-1，C)，m(n-2，C).....来依次求解，即可装包物品分别为（物品n）、（物品n-1，n）、（物品n-2，n-1，n）、……、（物品1，物品2，……物品n-1，物品n）。
最后求出的值即为最优值m(1，C)。
若求m(i,j)，此时已经求出m(i+1,j)，即第i+1个物品放入和不放入时这二者的最大值。
对于此时背包剩余容量j=0,1,2,3……C，分两种情况：(1)当w[i] > j，即第i个物品重量大于背包容量j时，m(i,j)=m(i+1,j)(2)当w[i] <= j，即第i个物品重量不大于背包容量j时，这时要判断物品i放入和不放入对m的影响。
若不放入物品i，则此时m(i,j)=m(i+1,j)若放入物品i，此时背包剩余容量为 j-w[i]，在子结构中已求出当容量k=0,1,2……C 时的最优值m(i+1,k)。
所以此时m(i,j)=m(i+1,j-w[i])+v[i]。
0-1背包问题的枚举算法一、问题概述0-1背包问题是一种经典的优化问题，给定一组物品，每种物品都有自己的重量和价值，而你有一个限制容量的背包。
目标是在不超过背包容量的情况下，选择物品使得总价值最大化。
然而，在某些情况下，所有的物品都不能被放入背包中，这时就需要用到0-1背包问题的枚举算法。
二、算法原理枚举算法的基本思想是从所有可能的物品组合中逐个尝试，找出满足条件的组合。
对于0-1背包问题，我们可以枚举所有可能的物品组合，对于每个组合，计算其总价值和当前背包的剩余容量，如果总价值大于当前背包容量所能获得的最大价值，那么就将这个物品放入背包中，并更新背包剩余容量和总价值。
如果当前物品的价值小于或等于当前背包容量所能获得的最大价值，那么就将这个物品标记为0（表示已经考虑过），并继续尝试下一个物品。
最终得到的组合就是最优解。
三、算法实现以下是一个简单的Python实现：```pythondefknapsack_enumeration(items,capacity):#初始化结果列表和当前价值result=[]current_value=0#枚举所有可能的物品组合foriinrange(len(items)):#标记当前物品为0（已考虑过）items[i][1]=0#计算当前物品的价值并更新总价值forjinrange(len(items)):ifj<i:#不考虑之前的物品对当前物品的价值影响current_value+=items[j][1]*items[i][0]/capacityelse:#考虑之前的物品对当前物品的价值影响（假设不考虑前一个物品的重量）current_value+=items[j][0]*(capacity-items[i][0])/capacity#将当前物品从物品列表中移除（放入背包中）delitems[i]#将当前价值添加到结果列表中result.append(current_value)returnresult```四、应用场景枚举算法在许多实际应用中都有应用，如计算机科学、运筹学、工程学等。
背包问题：0-1背包、完全背包和多重背包背包问题泛指以下这⼀种问题：给定⼀组有固定价值和固定重量的物品，以及⼀个已知最⼤承重量的背包，求在不超过背包最⼤承重量的前提下，能放进背包⾥⾯的物品的最⼤总价值。
这⼀类问题是典型的使⽤动态规划解决的问题，我们可以把背包问题分成3种不同的⼦问题：0-1背包问题、完全背包和多重背包问题。
下⾯对这三种问题分别进⾏讨论。
1.0-1背包问题0-1背包问题是指每⼀种物品都只有⼀件，可以选择放或者不放。
现在假设有n件物品，背包承重为m。
对于这种问题，我们可以采⽤⼀个⼆维数组去解决：f[i][j]，其中i代表加⼊背包的是前i件物品，j表⽰背包的承重，f[i][j]表⽰当前状态下能放进背包⾥⾯的物品的最⼤总价值。
那么，f[n][m]就是我们的最终结果了。
采⽤动态规划，必须要知道初始状态和状态转移⽅程。
初始状态很容易就能知道，那么状态转移⽅程如何求呢？对于⼀件物品，我们有放进或者不放进背包两种选择：（1）假如我们放进背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，这⾥的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。
⽽对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这⾥，我们要明⽩：要把这件物品放进背包，就得在背包⾥⾯预留这⼀部分空间。
（2）假如我们不放进背包，f[i][j] = f[i - 1][j]，这个很容易理解。
因此，我们的状态转移⽅程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])当然，还有⼀种特殊的情况，就是背包放不下当前这⼀件物品，这种情况下f[i][j] = f[i - 1][j]。
0-1背包问题背包问题：n种物品，每种物品有重量w和价值v，背包所能承受的最⼤重量为c。
如何挑选物品可以使总物品的价值最⼤。
0-1背包问题：限定每种物品的个数只能是0或1.如：5个物品，质量分别为3,5,7,8,9，价值分别为4,6,7,9,10。
背包所能承受重量为22.给物品从0开始编号，挑选物品1,3,4（价值分别为6,9,10）时，总价值最⼤为25，此时重量为22.运⽤动态规划思想，可以构造有效的⽅法。
算法基本思路：1.构造最优表，获取最⼤价值；构造表mv[0...n][0...c]，mv[i][j] 表⽰前 i 项物品（即0到i-1）中挑选物品放⼊承受重量为 j 的最⼤价值。
显然，当 i 为0即没有物品时，mv[0][*] = 0；当 j 为0即最⼤重量为0时，mv[*][0] = 0。
（*表⽰任意）对于mv[i][j]只有两种可能的情况，（要注意的是，i 表⽰前i 项物品，物品编号从0开始，即 i-1 表⽰第i 项物品）(1)当w[i-1] > j 即当前物品重量⼤于当前最⼤承受重量时，只能放弃当前物品即 mv[i][j] = mv[i-1][j]；(2)当w[i-1] <= j 即当前物品重量⼩于当前最⼤承受重量时，通过⽐较取此物品后的最⼤价值（即mv[i-1][j-w[i-1]] + v[i-1]）与不取此物品的最⼤价值（即mv[i-1][j]），挑出较⼤值即 mv[i][j] = max(mv[i-1][j], mv[i-1][j-w[i-1]])。
通过上述⾃底向上打表，可构造出最优值mv[n][c]。
2.通过最优表，获取构造路线即挑出可以得到最⼤价值的物品。
通过上述可知，当w[i-1] > j 时，mv[i][j] = mv[i-1][j]；当w[i-1] <= j 时，mv[i][j] = max(mv[i-1][j], mv[i-1][j - w[i-1]] + v[i-1])。
课程设计说明书设计题目： 0-1背包问题的动态规划算法设计专业：班级：设计人：山东科技大学2013年12月5日课程设计任务书学院：专业：班级：姓名：一、课程设计题目：二、课程设计主要参考资料（1）计算机算法设计与分析（第3版）王晓东著（2）三、课程设计应解决的主要问题（1） 0-1背包问题的动态规划算法设计（2）（3）四、课程设计相关附件（如：图纸、软件等）：（1）（2）五、任务发出日期： 2013-11-21 课程设计完成日期： 2013-12-5 指导教师签字：系主任签字：指导教师对课程设计的评语成绩：指导教师签字：年月日0-1背包问题的实现一、设计目的1.运用动态规划思想，设计解决上述问题的算法，找出最大背包价值的装法。
2.掌握动态规划的应用。
二、设计要求给定n种物品和一背包。
物品i的重量是wi，其价值为vi，背包的容量为C。
问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。
不能将物品装入背包多次，也不能只装入部分的物品。
0-1背包问题是一个特殊的整数规划问题。
三、设计说明（一）、需求分析1、问题描述：形式化描述：给定c >0, w i>0, v i>0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋∑w i x i≤c,且∑v i x i达最大.即一个特殊的整数规划问题。
2、最优子结构性质：设(y1,y2,…,y n)是(3.4.1)的一个最优解.则(y2,y3,…,y n)是下面相应子问题的一个最优解:证明:使用反证法。
若不然,设(z2,z3,…,z n)是上述子问题的一个最优解,而(y2,y3,…,y n)不是它的最优解。
显然有∑v i z i> ∑v i y i(i=2,…,n)且w1y1+ ∑w i z i<= c因此v 1 y 1+ ∑v i z i (i=2,…,n) > ∑v i y i , (i=1,…,n)说明(y 1,z 2,z 3,…,z n )是(3.4.1)0-1背包问题的一个更优解,导出(y 1,y 2,…,y n )不是背包问题的最优解,此为矛盾。
所以0-1背包问题具有最有子结构。
（二）、概要设计1、递推关系：设所给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-w i ,效益值增长了v i ；2、设计思路(1).由0-1背包问题的最优子结构性质，建立计算m[i][j]的递归式如下：i i i i w j w j j i m v w j i m j i m j i m <≤≥⎩⎨⎧-+---=0),1(}),1(),,1(max{),( n n nw j w j vj m <≤≥⎩⎨⎧=00),n ((2).查找装入背包物品的函数：从数组的最右下角开始寻找，如若m[i][c] != m[i-1][c]，则该第i 个物品就在背包中，将其从最大价值量中去掉，然后再接着寻找下一个在背包中的物品，直至i=0。
关键数据结构：一个二维数组，两个一维数组，两个整型变量 int n;//n 表示物品的种类double c;//表示背包重量的最大值double w[N],v[N];//分别表示物品的重量和价值double **p;//由于存放跳跃点函数模块：Type Knapsack(int n,Type c,Type v[],Type w[],Type **p,int x[]);//整理背包函数，找出最大价值void Traceback(int n,Type w[],Type v[],Type **p,int *head,int x[]);//找出所有在背包里的物品的函数3、算法的改进：由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。
跳跃点是这一类函数的描述特征。
在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。
如图所示。
对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。
表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]={(0，0)}。
函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j- w i)+ v i作max运算得到的。
因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集p[i+1]与函数m(i+1，j- w i)+ v i的跳跃点集q[i+1]的并集中。
易知，(s,t)∈q[i+1]当且仅当wi<=s<=c且(s-wi,t-vi)∈p[i+1]。
因此，容易由p[i+1]确定跳跃点集q[i+1]如下：q[i+1]=p[i+1]⊕(w i,v i)={(j+wi,m(i,j)+vi)|(j,m(i,j))∈p[i+1]}另一方面，设(a，b)和(c，d)是p[i+1]∪q[i+1]中的2个跳跃点，则当c>=a且d<b时，(c，d)受控于(a，b)，从而(c，d)不是p[i]中的跳跃点。
除受控跳跃点外，p[i+1]∪q[i+1]中的其他跳跃点均为p[i]中的跳跃点。
由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。
例：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。
跳跃点的计算过程如下：初始时p[6]={(0,0)}，(w5,v5)=(4,6)。
因此，q[6]=p[6]⊕(w5,v5)={(4,6)}。
p[5]={(0,0),(4,6)}。
q[5]=p[5]⊕(w4,v4)={(5,4),(9,10)}。
从跳跃点集p[5]与q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。
将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4]⊕(6，5)={(6，5)，(10，11)}p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3]⊕(2，3)={(2，3)，(6，9)}p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}q[2]=p[2]⊕(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。
（三）、详细设计#include <iostream>using namespace std;template<class Type>Type Knapsack(int n,Type c,Type v[],Type w[],Type **p,int x[]){int *head = new int[n+2];head[n+1]=0;p[0][0]=0;//p[][0]存储物品重量p[0][1]=0;//p[][1]存储物品价值，物品n的跳跃点（0，0）// left 指向p[i+1]的第一个跳跃点，right指向最后一个//拿书上的例子来说，若计算p[3]=0;则left指向p[4]的第一跳跃点（0 0）right指向（9,10）int left = 0,right = 0,next = 1;//next即下一个跳跃点要存放的位置head[n]=1;//head[n]用来指向第n个物品第一个跳跃点的位置for(int i=n; i>=1; i--){int k = left;//k指向p[ ]中跳跃点,移动k来判断p[]与p[]+（w v）中的受控点for(int j=left; j<=right; j++){if(p[j][0]+w[i]>c) break;//剩余的空间不能再装入i，退出for循环;Type y = p[j][0] + w[i],m = p[j][1] + v[i];//计算p[ ]+（w v）//若p[k][0]较小则(p[k][0] p[k][1])一定不是受控点，将其作为p[i]的跳跃点存储while(k<=right && p[k][0]<y){p[next][0]=p[k][0];p[next++][1]=p[k++][1];}//如果 p[k][0]==y而m<p[k][1]，则（y m）为受控点不存if(k<=right && p[k][0]==y){if(m<p[k][1])//对（p[k][0] p[k][1]）进行判断{m=p[k][1];}k++;}// 若p[k][0]>=y且m> =p[k][1],判断是不是当前i的最后一个跳跃点的受控点//若不是则为i的跳跃点存储if(m>p[next-1][1]){p[next][0]=y;p[next++][1]=m;}//若是，则对下一个元素进行判断。
while(k<=right && p[k][1]<=p[next-1][1]){k++;}}while(k<=right){p[next][0]=p[k][0];p[next++][1]=p[k++][1];//将i+1剩下的跳跃点作为做为i 的跳跃点存储}left = right + 1;right = next - 1;// 第i-1个物品第一个跳跃点的位置 head[0]指第0个物品第一个跳跃点的位置head[i-1] = next;}Traceback(n,w,v,p,head,x);return p[next-1][1];}//x[]数组存储对应物品0-1向量,0不装入背包，1表示装入背包template<class Type>void Traceback(int n,Type w[],Type v[],Type **p,int *head,int x[]){//初始化j,m为最后一个跳跃点对应的第0列及第1列//如上例求出的最后一个跳跃点为（8 15）j=8,m=15Type j = p[head[0]-1][0],m=p[head[0]-1][1];for(int i=1; i<=n; i++){x[i]=0;// 初始化数组；for(int k=head[i+1]; k<=head[i]-1;k++)// 初始k指向p[2]的第一个跳跃点（0 0）{//判断物品i是否装入，如上例与跳跃点(6 9)相加等于（8 15）所以1装入if(p[k][0]+w[i]==j && p[k][1]+v[i]==m){x[i]=1;//物品i被装入，则x[i]置1j=p[k][0];// j和m值置为满足if条件的跳跃点对应的值m=p[k][1];// 如上例j=6,m=9break;//再接着判断下一个物品}}}}int main(){double c;int n;cout << "请输入物品个数: ";cin >> n ;cout << endl << "请输入背包的承重：";cin >> c;double *w = new double[n+1];double *v = new double[n+1];int *x = new int[n+1];cout << endl << "请输入每个物品的重量 (w[i])和价值 (v[i]): " << endl;for(int i = 1; i <= n; i++)cin >> w[i] >> v[i];for(int i = 1;i <= n;i++)x[i]=0;double **p = new double *[50];for(int i=0;i<50;i++){p[i] = new double[2];}cout<<"背包能装的最大价值为："<<Knapsack(n,c,v,w,p,x)<<endl;cout<<"背包装下的物品编号为："<<endl;for(int i=1; i<=n; i++){if(x[i]==1){cout<<i<<" ";}}cout<<endl;for(int i=0;i<50;i++){delete p[i];}delete[] p;return 0;}四、运行结果及分析分析：上述算法的主要计算量在于计算跳跃点集p[i](1≤i ≤n)。
