|
|
???今天復(fù)習(xí)了動態(tài)規(guī)劃算法。01背包問題是一個典型的動態(tài)規(guī)劃問題。算法的證明過程比較復(fù)雜，但是計算過程并不難理解。
???
???假設(shè)有這樣的序列 n＝3 M=6 (物體數(shù)量為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);
}
|