TA的每日心情 | 开心 2021-12-13 21:45 |
---|
签到天数: 15 天 [LV.4]偶尔看看III
|
这个学期开的算法设计与分析课程老师说是研究生才要学的课,但是我们大二就要学!
虽然有难度,但还是要学滴。
上机课题目有一道0-1背包的问题,上课的时候由于没有听课。。所以只有自己再啃书本了。
代码虽然不长,但是还是。。很有。。技术含量的。
本人文笔不是很好,所以就 不多说啦!直接上菜!
问题描述:
给定N中物品和一个背包。物品i的重量是W[sub]i[/sub],其价值位V[sub]i[/sub] ,背包的容量为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<w[sub]i [/sub]
V(i,j)=max{V(i-1,j) ,V(i-1,j-w[sub]i[/sub])+v[sub]i[/sub]) } j>w[sub]i[/sub]
(1)式表明:如果第i个物品的重量大于背包的容量,则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的,即物品i不能装入背包;第(2)个式子表明:如果第i个物品的重量小于背包的容量,则会有一下两种情况:(a)如果把第i个物品装入背包,则背包物品的价值等于第i-1个物品装入容量位j-w[sub]i[/sub] 的背包中的价值加上第i个物品的价值v[sub]i;[/sub](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[
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)
21 V[j]=V[i-
1][j];
22
else
23 V[j]=max(V[i-
1][j],V[i-
1][j-w]+v);
24 j=C;
25
for(i=n-
1;i>=
0;i--)
26 {
27
if(V[j]>V[i-
1][j])
28 {
29 x=
1;
30 j=j-w;
31 }
32
else
33 x=
0;
34 }
35 printf(
"
选中的物品是:\n
");
36
for(i=
0;i<n;i++)
37 printf(
"
%d
",x);
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);
60
61 printf(
"
请分别输入物品的价值:\n
");
62
for(i=
0;i<n;i++)
63 scanf(
"
%d
",&v);
64
65 s=KnapSack(n,w,v,x,C);
66
67 printf(
"
最大物品价值为:\n
");
68 printf(
"
%d\n
",s);
69
70
71 }
|
|