|
|
今天复习了动态规划算法。01背包问题是一个典型的动态规划问题。算法的证明过程比较复杂，但是计算过程并不难理解。
假设有这样的序列 n＝3 M=6 (物体数量为3，背包能背的重量为6)
wi 2 3 4 (物体重量)
pi 1 2 5 (物体的价值)
初始化：Si={(P)}(待完成)
代码:
#include
"
stdio.h
"
#include
"
stdlib.h
"
#define MAXSIZE
1000
void
DKNAP(
int
*
,
int
*
,
int
,
int
);
void
PARTS(
int
*
,
int
*
,
int
*
,
int
*
,
int
,
int
);
void
main(
void
)
 
{
int
i,j,n,
*
w,
*
p,M;
 
if
(freopen(
"
input.txt
"
,
"
r
"
,stdin)
==
NULL)
{
printf(
"
can't open file 'input.txt'\n
"
);
exit(
-
1
);
 }
scanf(
"
%d
"
,
&
n);
scanf(
"
%d
"
,
&
M);
w
=
(
int
*
)malloc(sizeof(
int
)
*
n);
p
=
(
int
*
)malloc(sizeof(
int
)
*
n);
for
(i
=
0
;i
<
n;i
++
)
scanf(
"
%d
"
,
&
w[i]);
for
(i
=
0
;i
<
n;i
++
)
scanf(
"
%d
"
,
&
p[i]);
DKNAP(w,p,n,M);
 }
void
DKNAP(
int
*
w,
int
*
p,
int
n,
int
M)
{
int
*
f,l,h,k,next,u,i,j,pp,ww,m;
int
P[MAXSIZE],W[MAXSIZE];
f
=
(
int
*
)malloc(sizeof(
int
)
*
(n
+
1
));
P[
0
]
=
0
;
W[
0
]
=
0
;
f[
0
]
=
next
=
1
;
l
=
h
=
0
;
for
(i
=
0
;i
<
n;i
++
)
{
k
=
l;
j
=
h;
while
(W[j]
+
w[i]
>
M) j
--
;
u
=
j;
for
(j
=
l;j
<=
u;j
++
)
{
ww
=
W[j]
+
w[i];
pp
=
P[j]
+
p[i];
while
(k
<=
h
&&
W[k]
<
ww)
{
W[next]
=
W[k];
P[next]
=
P[k];
next
++
;
k
++
;
}
if
(k
<=
h
&&
W[k]
==
ww)
{
pp
=
pp
>
P[k]
?
pp:P[k];
k
++
;
}
if
(pp
>
P[next
-
1
])
{
P[next]
=
pp;
W[next]
=
ww;
next
++
;
}
while
(k
<=
h
&&
P[k]
<
P[next
-
1
] ) k
++
;
}
while
(k
<=
h)
{
P[next]
=
P[k];
W[next]
=
W[k];
next
++
;
k
++
;
}
f[i
+
1
]
=
next;
l
=
h
+
1
;
h
=
next
-
1
;
}
m
=
W[next
-
1
];
printf(
"
\np max is %d \n
"
,P[next
-
1
]);
PARTS(W,w,p,f,n
-
1
,m);
}
void
PARTS(
int
*
W,
int
*
w,
int
*
p,
int
*
f,
int
i,
int
m)
{
int
flag,j,k;
while
(m
>
0
&&
i
>
0
)
{
flag
=
0
;
for
(j
=
f[i
-
1
];j
<
f[i];j
++
)
if
(W[j]
==
m)
{
flag
=
1
;
break
;
}
if
(flag
==
0
)
{
printf(
"
%d\n
"
,i);
m
-=
w[i];
}
i
--
;
}
if
(m
>
0
) printf(
"
%d\n
"
,i);
}
|