问题描述:
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??
在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能讲物品i装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。
问题分析:令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值,则可以得到如下的动态规划函数:
(1) V(i,0)=V(0,j)=0
(2) V(i,j)=V(i-1,j) j<wi
V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
(1)式表明:如果第i个物品的重量大于背包的容量,则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的,即物品i不能装入背包;第(2)个式子表明:如果第i个物品的重量小于背包的容量,则会有一下两种情况:(a)如果把第i个物品装入背包,则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包,则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然,取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。
1 #include<stdio.h>
2
3 int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
4 int max(int a,int b)
5 {
6 if(a>=b)
7 return a;
8 else return b;
9 }
10
11 int KnapSack(int n,int w[],int v[],int x[],int C)
12 {
13 int i,j;
14 for(i=0;i<=n;i++)
15 V[i][0]=0;
16 for(j=0;j<=C;j++)
17 V[0][j]=0;
18 for(i=0;i<=n-1;i++)
19 for(j=0;j<=C;j++)
20 if(j<w[i])
21 V[i][j]=V[i-1][j];
22 else
23 V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
24 j=C;
25 for(i=n-1;i>=0;i--)
26 {
27 if(V[i][j]>V[i-1][j])
28 {
29 x[i]=1;
30 j=j-w[i];
31 }
32 else
33 x[i]=0;
34 }
35 printf("选中的物品是:\n");
36 for(i=0;i<n;i++)
37 printf("%d ",x[i]);
38 printf("\n");
39 return V[n-1][C];
40
41 }
42
43 void main()
44 {
45 int s;//获得的最大价值
46 int w[15];//物品的重量
47 int v[15];//物品的价值
48 int x[15];//物品的选取状态
49 int n,i;
50 int C;//背包最大容量
51 n=5;
52 printf("请输入背包的最大容量:\n");
53 scanf("%d",&C);
54
55 printf("输入物品数:\n");
56 scanf("%d",&n);
57 printf("请分别输入物品的重量:\n");
58 for(i=0;i<n;i++)
59 scanf("%d",&w[i]);
60
61 printf("请分别输入物品的价值:\n");
62 for(i=0;i<n;i++)
63 scanf("%d",&v[i]);
64
65 s=KnapSack(n,w,v,x,C);
66
67 printf("最大物品价值为:\n");
68 printf("%d\n",s);
69
70
71 }
3 int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
4 int max(int a,int b)
5 {
6 if(a>=b)
7 return a;
8 else return b;
9 }
10
11 int KnapSack(int n,int w[],int v[],int x[],int C)
12 {
13 int i,j;
14 for(i=0;i<=n;i++)
15 V[i][0]=0;
16 for(j=0;j<=C;j++)
17 V[0][j]=0;
18 for(i=0;i<=n-1;i++)
19 for(j=0;j<=C;j++)
20 if(j<w[i])
21 V[i][j]=V[i-1][j];
22 else
23 V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
24 j=C;
25 for(i=n-1;i>=0;i--)
26 {
27 if(V[i][j]>V[i-1][j])
28 {
29 x[i]=1;
30 j=j-w[i];
31 }
32 else
33 x[i]=0;
34 }
35 printf("选中的物品是:\n");
36 for(i=0;i<n;i++)
37 printf("%d ",x[i]);
38 printf("\n");
39 return V[n-1][C];
40
41 }
42
43 void main()
44 {
45 int s;//获得的最大价值
46 int w[15];//物品的重量
47 int v[15];//物品的价值
48 int x[15];//物品的选取状态
49 int n,i;
50 int C;//背包最大容量
51 n=5;
52 printf("请输入背包的最大容量:\n");
53 scanf("%d",&C);
54
55 printf("输入物品数:\n");
56 scanf("%d",&n);
57 printf("请分别输入物品的重量:\n");
58 for(i=0;i<n;i++)
59 scanf("%d",&w[i]);
60
61 printf("请分别输入物品的价值:\n");
62 for(i=0;i<n;i++)
63 scanf("%d",&v[i]);
64
65 s=KnapSack(n,w,v,x,C);
66
67 printf("最大物品价值为:\n");
68 printf("%d\n",s);
69
70
71 }
相关推荐
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
贪婪法解决01背包问题贪婪法解决01背包问题贪婪法解决01背包问题贪婪法解决01背包问题
01背包问题的源代码,C语言编写,绝对可以运行。
01背包问题是一个很经典的问题,在这里我用回溯法解决。希望大家一起来探讨呀!
课程作业,实现算法实践书后的例题,实现01背包问题
免疫克隆解决01背包问题,将免疫概念及其理论应用于遗传算法,在保留原算法优良特性的前提下,力图有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象,这种算法称为免疫算法...
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
利用动态规划算法实现了01背包问题,并取得了良好的效果。
分治法求01背包问题c语言 已调通
回溯法和动态规划法解01背包问题,控制台应用程序,代码没有编译完成,请自行编译
01背包问题解决方法不少,动态规划是其中之一,动态规划的问题解题思路都差不多(一些浅见),基本要素是最优子结构性质,子问题重叠性质,自底向上的求解方法。只要了解了基本要素,那么这种题型也会更好理解。本题...
01背包问题的贪心算法,详细解析,令你很快懂的01背包问题中的贪心算法思想
文档详细地解释了动态规划法解决01背包问题,包括算法设计思想、算法改进思想、存储结构、算法实现,是一篇来自计算机读报的文章,适合各位对动态规划存在疑问的同学好好品读。
C语言实现01背包问题 回溯法 算法分析题答案
0-1背包问题测试数据,内含多组测试数据,物品的价值量及其重量,复制粘贴即可使用
本代码大量注释,便于理解。回溯法解决01背包问题,相对于动态规划来说,我们首先得了解问题的解空间,了解解空间的组织结构,最后搜索解空间,其中加入约束条件和限界条件是关键,否则就是穷举了。
01背包问题,四种方法(动态规划、贪心、回溯、分支限界)
C++编写的01背包问题,用的动态规划的思想,用于学习算法课程,内包含程序解决问题及源代码,可以运行。
经典遗传算法(SGA)解01背包问题的python代码实现,说明如下: 1.采用经典的二进制编码,选择算子为轮盘赌选择,交叉算子为两点交叉,变异算子为反转(单点)变异 2.可调的参数为:gen,pc,pm,popsize,n,w,c,W,M 3.两...
本程序是用Java开发的,使用回溯法解决01背包问题。程序比较易懂。输入分三行,第一行是物品数量N和背包容量C,第二行是物品重量数组,第三行是价值重量数组。然后输出最优解。