1NGÂN HÀNG  THI
Môn: TOÁN RI RC 1
Dùng cho h HTX, ngành Công ngh thông tin
S tín ch: 3 1
/ Hãy cho bit khng đnh nào di đây không phi là mt mnh đ:
a
2 + 1 < 3
b
3 * 2 !=6
c
X + 1 = 2
d
3 - 1 > 2

2
/ Gi s p và q là các mnh đ. Hãy cho bit đnh ngha đúng ca mnh đ .
a
Là mt mnh đ mà nó ch nhn giá tr T khi và ch khi p, q nhn giá tr T. Nhn giá tr F
khi và ch khi hoc p, q,
hoc c hai nhn giá tr F.
b
Là mt mnh đ ch đúng khi mt trong p hoc q là đúng và sai trong các trng hp khác
còn li.
c

còn li.
b
Là mt mnh đ mà nó ch nhn giá tr T khi và ch khi p, q nhn giá tr T. Nhn giá tr F
khi và ch khi hoc p, q,
hoc c hai nhn giá tr F.
c
Là mt mnh đ nhn giá T khi và ch khi p nhn giá tr F hoc p và q cùng nhn giá tr T.
Nhn giá tr F khi và
ch khi p nhn giá tr T và q nhn giá tr F. HC VIN CÔNG NGH BU CHÍNH VIN THÔNG
Km10 ng Nguyn Trãi, Hà ông-Hà Tây
Tel: (04).5541221; Fax: (04).5540587
Website:
http://www.e-ptit.edu.vn
; E-mail: [email protected] 2
d
Là mt mnh đ mà nó ch nhn giá tr T khi và ch khi ít nht mt trong hai mnh đ p, q
nhn giá tr T.
Nhn giá tr F khi và ch khi c p, q đu nhn giá tr F.

5
/ Gi s p và q là các mnh đ. Hãy cho bit đnh ngha đúng ca mnh đ .
a
Là mt mnh đ ch đúng khi mt trong p hoc q là đúng và sai trong các trng hp khác
còn li.

7
/ âu là đnh ngha mnh đ hng đúng trong logic mnh đ
a
Là mt mnh đ ch đúng khi các mnh đ thành phn nhn giá tr T.
b
Mt mnh đ phc hp mà luôn luôn đúng vi bt k các giá tr chân lý ca các mnh đ
thành phn đc
gi là hng đúng (tautology).
c
Mt mnh đ luôn luôn sai vi mi giá tr chân lý ca các mnh đ thành phn ca nó đc
gi là mâu thun.
d
Là mt mnh đ ch đúng khi các mnh đ thành phn nhn giá tr F.

8
/ âu là đnh ngha mnh đ mâu thun trong logic mnh đ
a
Là mt mnh đ ch đúng khi các mnh đ thành phn nhn giá tr T.
b
Mt mnh đ luôn luôn sai vi mi giá tr chân lý ca các mnh đ thành phn ca nó đc
gi là mâu thun.
c
Mt mnh đ phc hp mà luôn luôn đúng vi bt k các giá tr chân lý ca các mnh đ
thành phn đc
gi là hng đúng (tautology).
d
Là mt mnh đ ch đúng khi các mnh đ thành phn nhn giá tr F.

9
/ Hãy cho bit đâu là lut “ng nht” trong các tng đng logic di đây:

d 12
/ Hãy cho bit đâu là lut “Ph đnh kép” trong các tng đng logic di đây:
a

b

c

d 13
/ Hãy cho bit đâu là lut “Lut giao hoán” trong các tng đng logic di đây:
a

b

c

d 14
/ Hãy cho bit đâu là lut “Lut kt hp” trong các tng đng logic di đây:
a

b

a
Nó là hi ca các mnh đ ph đnh.
b
Nó hi ca các mnh đ kéo theo.

4
c
Nó là hi ca các mnh đ tuyn.
d
Nó là hi ca các mnh đ kéo theo nhau.

18
/ Cho A và B là hai tp hp. Phép hp ca A và B đc ký hiu là là:
a
Tp cha tt c các phn t thuc A và đng thi thuc B.
b
Tp cha tt c các phn t hoc thuc tp hp A hoc thuc tp hp B.
c
Tp bao gm nhng phn t không thuc A.
d
Tp cha các phn t thuc tp hp A nhng không thuc tp hp B.

19
/ Cho A và B là hai tp hp. Phép giao ca A và B đc ký hiu là là:
a
Tp bao gm nhng phn t không thuc A.
b
Tp cha các phn t thuc tp hp A nhng không thuc tp hp B.
c
Tp cha tt c các phn t thuc A và đng thi thuc B.

b

c

d

A
A= 23
/ Cho A là mt tp hp hu hn, U là tp v tr. Hãy cho bit đâu là lut nut trong s các lut
di đây:
a

b

A
A=

c

d

24
/ Cho A là mt tp hp hu hn, U là tp v tr. Hãy cho bit đâu là lut nut trong s các lut
di đây:
a

b


bc

d
27
/ Cho A, B, C là các tp hp. Hãy cho bit đâu là lut kt hp trong s các lut di đây:

abc

;
A
BABABA B∪=∩ ∩= ∪d 28
/ Cho A, B, C là các tp hp. Hãy cho bit đâu là lut phân phi trong s các lut di đây:

a


30
/ Hãy cho bit đâu là ni dung c bn nht ca bài toán đm:
a
Ch ra mt công thc tính nghim cho bài toán đang xét.

b
a ra mt phng pháp vét cn sao cho không lp li các cu hình đã xét và không b xót
mt cu hình nào.

c
Ch ra mt nghim ca bài toán hoc chng minh bài toán không có nghim.

d
Ch ra nghim tt nht, xu nht, tt nht trong tp phng án xu, hoc xu nht trong các
phng án tt. 31
/ Hãy cho bit đâu là ni dung c bn nht ca bài tn ti
a
Ch ra nghim tt nht, xu nht, tt nht trong tp phng án xu, hoc xu nht trong các
phng án tt.

b
Ch ra mt nghim ca bài toán hoc chng minh bài toán không có nghim.
c
a ra mt phng pháp vét cn sao cho không lp li các cu hình đã xét và không b xót
mt cu hình nào.


Nu A và B là hai tp hp thì :

d
Nu có N đ vt đc đt vào K hp thì s tn ti mt hp cha ít nht hp 34
/ Hãy cho bit đâu là ni dung ca nguyên lý bù tr phát biu trên hai tp hp hu hn A và B:

a
Nu A và B là hai tp hp ri nhau thì :

b
Nu có N đ vt đc đt vào K hp thì s tn ti mt hp cha ít nht hp

c
Nu A và B là hai tp hp thì :

d
Nu A và B là hai tp hp thì : 35
/ Hãy cho bit đâu là ni dung ca nguyên lý Dirichlet phát biu trên quan đim ca lý thuyt
tp hp:

a
Nu A và B là hai tp hp ri nhau thì :

b

n
là nhng tp hp ri nhau thì: d
Gi s A
1
, A
2
, . ., A
m
là nhng tp hu hn. Khi đó:
37
/ Hãy cho bit đâu là ni dung ca nguyên nhân tng quát phát biu trên quan đim ca lý
thuyt tp hp:

a
Nu có N đ vt đc đt vào K hp thì s tn ti mt hp cha ít nht hp
b
Gi s A
1
, A
2
, . ., A
m
là nhng tp hu hn. Khi đó:


Là mt b không k th t gm k thành phn khác nhau ly t n phn t đã cho.

d
Là mt cách xp có th t n phn t đó. 39
/ Chnh hp không lp chp k ca n phn t

7
a
Là mt b không k th t gm k thành phn khác nhau ly t n phn t đã cho.

b
Là b có th t gm k thành phn ly t n phn t ca tp đã cho.
c
Là b có th t gm k thành phn ly ra t n phn t đã cho. Các phn t không đc lp
li.

d
Là mt cách xp có th t n phn t đó. 40
/ Ta gi các hoán v ca n phn t

a
Là mt cách xp có th t n phn t đó.
b
Là b có th t gm k thành phn ly t n phn t ca tp đã cho.

n!

b
n! / k!(n-k)!

c
n
kd
n!/(n-k)! 43
/ S các các chnh hp không lp chp k ca n là n
k
.

a
n
kb
n! / k!(n-k)!

c
n!/(n-k)!
d

n!/(n-k)!

d
n! / k!(n-k)! 46
/ H thc truy hi ca dãy s { A
n
} là:

a
Công thc biu din a
n
qua mt hay nhiu s hng đi trc ca dãy

b
Công thc biu din a
n
thông qua n

c
Công thc biu din:
knknnn
acacaca
−−−
+
+
+
= 

Công thc biu din a
n
thông qua n

c
Công thc biu din a
n
qua mt hay nhiu s hng đi trc ca dãy

d
Công thc biu din:
knknnn
acacaca
−−−
+
+
+
= 
2111
, trong đó c
1
,c
2
, . ., c
k
là các s thc
và


d
2.(N-1) 50
/ T bng ch cái ting Anh có th to ra đc bao nhiêu xâu kí t có đ dài N.

a
26
Nb
26.(N-1)
c
26N

d
N
26
51
/ Cn b trí thc hin N chng trình trên mt máy tính. Hi có bao nhiêu cách b trí khác
nhau.

a
N

a
Ít nht mt t cùng bt đu bng mt ch cái.

b
Nhiu nht hai t cùng bt đu bng mt ch cái.
c
Ít nht hai t cùng bt đu bng mt ch cái.

d
Nhiu nht mt t cùng bt đu bng mt ch cái. 54
/ Lit kê là phng pháp:

a
a ra mt công thc cho li gii bài toán
b Ch ra nghim tt nht theo mt ngha nào đó ca bài toán.

c
a ra danh sách tt c các cu hình t hp có th có.

d
Ch ra mt nghim hoc chng minh bài toán không có nghim.

955
/ Mt thut toán lit kê phi đm bo:

Bc phân tích và bc thay th ngc li
b
Bc tính toán và phân tích

c
Bc thay th ngc li và phân tích

d
Bc phân tích và bc tính toán 58
/ Phng pháp sinh có th áp dng đ gii lp các bài toán tha mãn các điu kin:
a
Có th xác đnh đc mt th t trên tp các cu hình t hp cn lit kê.
toán sinh ra cu hình k tip t mt cu hình cha phi là cui cùng.

b
Xác đnh đc mt th t trên tp các cu hình, bit cu hình đu tiên và cu hình cui
cùng; Xây dng đc mt thut

c
Xác đnh đc cu hình t hp đu tiên và cu hình cui cùng.
d
Xây dng đc thut toán t cu hình xác đnh đ đa ra cu hình k tip. 59
/ Ni dung chính ca thut toán quay lui là:
a


c
P(b) >= P(b’); trong đó P(b), P(b’) là s có biu din nh phân tng ng vi b và b’.

d
P(b) > P(b’); trong đó P(b), P(b’) là s có biu din nh phân tng ng vi b và b’. 61
/ Ta nói tp con a = a
1
a
2
. . . a
k
đi trc tp con a’ = a
1
’a
2
’. . .a
k
’ theo th t t đin nu tìm
đc ch s j ( 1 <= j <= k )
sao cho:

a
a
1
< a
1

j
.

c
a
1
<= a
1
’, a
2
£ a
2
’, . . ., a
j-1
<= a’
j-1
, a
j
< a’
j
.

d
a
1
= a
1
’, a
2
= a

a
1
< a
1
’, a
2
< a
2
’, . . ., a
k-1
< a’
k-1
, a
k
< a’
k
.

10
b
a
1
= a
1
’, a
2
= a
2
’, . . ., a
k-1

= a
1
’, a
2
= a
2
’, . . ., a
k-1
= a’
k-1
, a
k
< a’
k
. 63
/ Cho tp hp U = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. Hãy cho bit tp con nào ca U di đây tng
ng vi xâu bít nh phân
b = “0 1 0 1 0 1 0 1 0 1”:

a
{ 1, 3, 5, 7, 9}

b
{ 0, 2, 4, 6, 8}

c
{ 0, 1, 2, 5, 9}


b
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
c
{ 0, 2, 4, 6, 8}

d
{ 1, 3, 5, 7, 9} 66
/ Cho tp hp U = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, Bit tp A tng ng vi xâu bít nh
phân “1 0 1 0 1 0 1 0 1 0”,
B : tng ng vi xâu bít nh phân “0 1 0 1 0 1 0 1 0 1”. Hãy cho bit tp con nào ca U tng
ng vi tp a
{ 0, 2, 4, 6, 8}
b
{ 1, 3, 5, 7, 9}

c
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

d
67
69
/ Hoán v nào di đây là hoán v k tip ca hoán v 2 1 3 4 5 6 7 8 9

a
2 3 1 4 5 6 7 8 9

b
2 1 4 3 5 6 7 8 9
c
3 1 2 4 5 6 7 8 9

d
2 1 3 4 5 6 7 9 8 70
/ Cho tp A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Hãy cho bit tp con 6 phn t nào k tip sau tp con
{ 2, 3, 4, 5, 6, 7}

a
{ 2, 4, 5, 6, 7, 8}

b
{ 2, 3, 4, 5, 6, 8}

c
{ 3, 4, 5, 6, 7, 8}
d

{ A, D, F, H, J}

cd
{ B, E, G, I, K} 73
/ Cho tp hp U = { A, B, D, E, F, G, H, I, J, K }, Bit tp P tng ng vi xâu bít
nh phân “1 0 1 0 1 0 1 0 1 0”,
Q : tng ng vi xâu bít nh phân “0 1 0 1 0 1 0 1 0 1”. Hãy cho bit tp con nào ca U tng
ng vi tp

a
{ A, B, C, D, E, F, G, H, I, J}

bc
{ A, D, F, H, J}

d
{ B, E, G, I, K} 74
/ Cho tp hp U = { A, B, D, E, F, G, H, I, J, K }, Bit tp P tng ng vi xâu bít

/ Phng án đem li giá tr nh nht hoc ln nht cho hàm mc tiêu đc gi là:

a
Mt phng án ca bài toán.
b
Phng án ti u ca bài toán.

c
Tp các phng án ti u.

d
Giá tr ti u ca bài toán 77
/ Giá tr đc gi là:

a
Giá tr ti u ca bài toán.

b
Mt giá tr ca hàm mc tiêu.
c
Mt phng án ti u.

d
Phng án ti u ca bài toán. 78

d
Bài toán “Cái túi”. 80
/ Hãy cho bit tên ca bài toán ti u kinh đin di đây:
Tìm
min { f(x) : g(x) £b }; vi
i
n
i
i
xcxf
∑
=
=
1
)(
;
i
n
i
i
xaxg
∑
=
=
1
)(
; x

a
Bài toán “Cho thuê máy”.

b
Bài toán “Phân công”.

c
Bài toán “Cái túi”.

d
Bài toán “Ngi du lch”. 13
82
/ Cho p và q là hai mnh đ. Hãy ch ra đâu là mnh đ hng đúng trong s các mnh đ di
đây:

a

p
p∩¬b

p
p∪¬

pq→¬
84
/ Cho p và q là hai mnh đ. Hãy ch ra tng đng logic ca mnh đ

abcd 85/ Cho p và q là hai mnh đ. Hãy ch ra tng đng logic ca mnh đ:

abc



d
88
/ Cho p và q là các mnh đ. Hãy ch ra tng đng logic ca mnh đ:

abcd
89
/ Cho A, B, C là các tp hp. Hãy ch ra đng thc ca tp:

14
ab


cd
92
/ Cho A, B, C là các tp hp. Hãy ch ra đng thc ca tp

abcd93
/ Trong 100 ngi có:

a
Ít nht ngi sinh nht cùng mt tháng.

b
Nhiu ít nht ngi sinh nht cùng mt tháng.

khác nhau ch ta có th đi?

a
( n (n-1))/2

b
(n-1)!

c
( n!)

d
( n (n-1)) 96
/ Có bao nhiêu s nguyên không ln hn 1000 chia ht cho 7 hoc 11?

a
200

b
220

c
120

15
d
20


d
7260 99
/ Hi trong tp X = { 1, 2, . ., 10000} có bao nhiêu s không chia ht cho bt c s nào trong
các s 3, 4, 7

a
7261

b
726

c
727

d
7260

100/ Có bao nhiêu xâu nh phân đ dài 10 bt đu bi 00 hoc kt thúc bi 11.

a
48

b
84

c


b
12

c
25

d
30

103
/ Lp toán hc ri rc có 25 sinh viên gii tin hc, 13 sinh viên gii toán và 8 sinh viên gii
c toán và tin hc. Hi lp
có bao nhiêu sinh viên nu mi sinh viên hoc gii toán hoc hc gii tin hc hoc gii c hai
môn?

a
30

b
12

c
13

d
25

16


b
Nâng a lên ly tha n -1 (a
n-1
).

c
Cng n -1 ln s a ( (n-1) a).

d
Nâng s a lên ly tha n (a
n
).

106
/ Thut toán đ qui di đây tính:
int function1(int a, int b){
if(a==0) return(b);
return(function1(b%a,a));

}

a
S nh nht trong hai s a và b.

b
Bi s chung nh nht ca a và b.

c
S ln nht trong hai s a và b.


}

a
S Fibonacci th n.

b
Tng hai s nguyên liên tip n và n-1.

c
Tng n s t nhiên đu tiên.

d
S nguyên t th n.

109
/ Thut toán đ qui di đây tính:
int function1(int n){

17
if(n==1) return(1);
else if(n==2) return(1);
return(function1(n-1)+function1(n-2));

}

a
Tng hai s nguyên liên tip n và n-1.

b
S nguyên t th n.


d
Sinh hoán v k tip ca B = 1, 2, 3, ,n.

111
/ Thut toán di đây dùng đ:
void Function1(int *C, int k, int n){
int i,j; i = k;
while(i>0 && C[i]==n-k+i) i ;
if(i>0) { C[i]= C[i]+1;
for(j=i+1; j<=k; j++) C[j] = C[i]+j-i;
}
}

a
Sinh xâu nh phân k tip ca xâu C = C
1
C
2
C
n
.

b
Sinh hoán v k tip ca C = 1, 2, 3, ,n.

c
Sinh cách chia k tip n thành tng các s nguyên nh hn n.

d

Sinh xâu nh phân k tip ca xâu P = P
1
P
2
P
n
.

113/ Thut toán đ qui di đây dùng đ:
void Function1(int i){
for(int j=0; j<=1;j++){ B[i]=j;
if(i==n-1) Result();
else Function1(i+1);
}
}
a
Lit kê các xâu nh phân đ dài n.

b
Lit kê các tp con j phn t k tip ca tp n phn t

c
Lit kê các hoán v ca 1, 2, 3, ,n.

d
Lit kê các cách chia n thành tng các s nguyên nh hn n.


else Function1(i+1);
}
}
a
Lit kê các cách chia n thành tng các s nguyên nh hn n.

b
Lit kê các hoán v ca 1, 2, 3, ,n.

c
Lit kê các tp con j phn t ca tp n phn t

d
Lit kê các xâu nh phân đ dài n.

116
/ Hãy cho bit tp các phng án ca bài toán “Cái túi”:

a
Tp các phng án D = { (x
1
, x
2
, , x
n
):
∑

Tp các phng án D = { (x
1
, x
2
, , x
n
):
∑
=
≤
n
i
ii
bxa
1
, x
i

{0, 1 }, a
i
, b>0 ( 1 i n.}
b
Tp các phng án trong đó I = { 1, 2, m }, S là
tp các tp con ca I.

c
Tp các phng án ca n s t nhiên { 1, 2, . ., n }}

d
Tp các phng án là hoán v ca 2, , n và p(1)=1.

Tp các phng án là hoán v ca 2, , n và p(1)=1.

d
Tp các phng án trong đó I = { 1, 2, m }, S là
tp các tp con ca I.

119
/ Hãy cho bit tp các phng án ca bài toán “Phân công”:

a
Tp các phng án là hoán v ca 2, , n và p(1)=1.
b
Tp các phng án trong đó I = { 1, 2, m }, S là
tp các tp con ca I.

c
Tp các phng án D = { (x
1
, x
2
, , x
n
):
∑
=
≤
n
i
ii
bxa


abcd122
/ Cho p, q là các mnh đ. Hãy ch ra mnh đ nào là hng đúng trong s các mnh đ di
đây:
a

bc20
d123
/ Cho p, q là các mnh đ. Hãy ch ra mnh đ nào là hng đúng trong s các mnh đ di

/ Cho p, q là các mnh đ. Hãy ch ra mnh đ nào là hng đúng trong s các mnh đ di
đây:

abcd126/ Cho p, q là các mnh đ. Hãy ch ra mnh đ nào là hng đúng trong s các mnh đ di
đây:

ab

cd

127
/ Có bao nhiêu hàm đn ánh xác đnh t mt tp A có m phn t nhn giá tr trên tp B có n


d
n(n-1) (n-2) . . .(n-m+1)

129
/ Mt d án đánh s đin thoi có dng NYX NNX XXXX.Trong đó, X là các s t 0 đn , Y
là các s hoc 0 hoc 1, N là
các s t 2 đn 9, hi có nhiu nht là bao nhiêu s đin thoi khác nhau đc đánh s?

a
64. 10
6b
1024. 10
6c
8.10
621
d
512. 10
6
a
1/n

b
e/n

c
(1/n) *(e/n)

d
e
-1132/ m s hàm t tp có k phn t vào tp có n phn t.

a
( n
k
)

b
(n -k)!

c
( k
n
)

d

( n - 2) hoc thc s tng, hoc thc s gim.

b
( n +2 ) hoc thc s tng, hoc thc s gim.

c
( n -1) hoc thc s tng, hoc thc s gim.

d
( n +1) hoc thc s tng, hoc thc s gim.

135
/ Gi s trong mt nhóm 6 ngi mi cp hai ngi hoc là bn, hoc là thù ca nhau. Khi đó:

a
có ba ngi là thù ca nhau

b
Trong nhóm không tn ti ba ngi là bn ca nhau hoc là k thù ca nhau.

c
có ba ngi là bn ca nhau

d
trong nhóm có ba ngi là bn ca nhau hoc là k thù ca nhau.
136
/ Kt qu nào đúng trong s nhng kt qu di đây sau khi thc hin thut toán:

double function1(float a, int n){
if(n==0) return(1);

Function1(8, 12) = 8.

c
Function1(12, 8) = 4.

d
Function1(12, 8) = 24.

138
/ Kt qu nào đúng trong s nhng kt qu di đây sau khi thc hin thut toán:

long function1(int n){
if(n==0) return(1);
return(n*function1(n-1));

}

a
Function1(3) = 24.

b
Function1(4) = 100.

c
Function1(2) = 1.

d
Function1(5) = 120.

139/ Kt qu nào đúng trong s nhng kt qu di đây sau khi thc hin thut toán:


a
Function1(5) = 3

b
Function1(6) = 5

c
Function1(4) = 1

d
Function1(7) = 13

141
/ Cho B = { 1, 0, 1, 0, 1, 0, 1, 1, 1, 0}, n=10. Kt qu nào đúng trong s nhng kt qu di
đây sau khi thc hin thut toán:
23
void Function1(int *B, int n){
int i = n-1;
while(i>=0 && B[i]){B[i]=0; i ; }
B[i]=1;
}
a
Function1(B,n) = { 0, 1, 1, 0, 1, 0, 1, 1, 1, 0}

d
C[ ] = { 3, 4, 5, 6, 7, 8}

143/ Cho P = { 1, 2, 5, 7, 4, 8, 3, 9, 6}, n=9. Kt qu nào đúng trong s nhng kt qu di đây
sau khi thc hin thut toán Function1(P, n):void Function1(int *P, int n){
int j, k, r, s, temp;j = n-2;
while(j>=0 && P[j]>P[j+1]) j ;
if(j>=0){ k=n-1;
while(P[j]>P[k]) k ;
temp = P[j]; P[j]=P[k]; P[k]=temp;
r=j+1; s=n-1;
while(r<s){
temp=P[r];P[r]=P[s]; P[s]=temp;
r++; s ;
}
}
}
a
P = { 1, 2, 5, 7, 4, 8, 9, 3, 6}

b
P = { 1, 2, 5, 7, 4, 8, 6, 3, 9}

c

/ Gi D là tp các phng án ca bài toán “Ngi du lch”. Hãy cho bit đâu là hàm mc tiêu
ca bài toán cái
túi trong s các hàm di đây:

a
| N
j
| là s các bít 1 ca xâu nh phân N
j
đ dài n.

bc
Trong đó là hoán v ca 1, 2, , n; C
ij
>0

d146/ Gi D là tp các phng án ca bài toán “Cho thuê máy”. Hãy cho bit đâu là hàm mc tiêu
ca bài toán cái
túi trong s các hàm di đây:

a
Trong đó là hoán v ca 1, 2, , n. C
ij
>0

∈
|:|)(
; | N
j
| là s các bít 1 ca xâu nh phân N
j
đ dài n.

cd148/ Thut toán nhánh cn có th đc áp dng gii bài toán ti u đt ra nu nh có th tìm đc
mt hàm
g

25
xác đnh trên tp tt c các phng án b phn sao cho:

a

vi mi li gii b phn (a
1
, a
2
, . ., a
k
), và vi mi k = 1, 2, . .

149
/  gii quyt bài toán cái túi bng thut toán nhánh cn, ta gi thit:

a

n
n
a
c
a
c
a
c

2
2
1
1
; trong đó a
i
, c
i
là trng lng và giá tr s dng ca đ vt i.

b

n
n
a
c

; trong đó a
i
, c
i
là trng lng và giá tr s dng ca đ vt i.

d

n
n
a
c
a
c
a
c
≤≤≤ 
2
2
1
1
; trong đó a
i
, c
i
là trng lng và giá tr s dng ca đ vt i.