Các bài toán duyệt
Balo
Cho một chiếc balô có thể đựng được k kg, trong chuyến đi picnic sắp tới bạn có n món đồ muốn mang theo, món đồ thứ i có khối lượng là a[i] kq , và giá trị là t[i]. Hãy tìm cách mang những món đồ nào để tổng khối lượng không qúa k và tổng giá trị là lớn nhất ( N <=30).
Du lịch
Cho N thành phố , khoảng cách từ thành phố i đến thành phố j là a[i,j]. Một người du lịch xuất phát từ thành phố 1 và cần đi đến tất cả các thành phố mỗi thành phố đúng một lần, sau đó quay lại thành phố 1 . Hãy tìm một lịch trình cho người du lịch đó với tổng độ dài đường đi là bé nhất. ( N<=10)
Chia kẹo
Có N gói kẹo cần chia cho hai lớp a và b, biết rằng gói kẹo thứ i có a[i] chiếc, hãy tìm cách chia kẹo sao cho số lượng chênh lệch kẹo giữa hai lớp là ít nhất. (N<=30)
Xếpviệc 1
Có N người cần thực hiện N công việc, mỗi người thực hiện một công việc và mỗi công việc do một người thực hiện, biết rằng người i thực hiện công việc j thì sẽ hết a[i,j] đơn vị thời gian, hãy tìm cách thực hiện các công việc sao cho tông thời gian thực hiện là ít nhất. ( n<=15)
Xếp việc 2
Cho N công việc, công việc thứ i thực hiện hết t[i] đơn vị thời gian, nếu như thời gian hoàn thành trước c[i] thì sẽ thu được lợi nhuận là p[i]. Hãy tìm cách thực hiện các công việc sao cho tổng lợi nhuận thu được là lớn nhất. ( N <=30)
Đĩa Hát.
Trên thị trường hiện đang có N đĩa hát được bán, đĩa hát thứ i có chứa các bài hát x1, x2, .. xk và giá thành là t[i]. Hãy tìm cách mua các đĩa hát sao cho có đủ các bài hát từ 1 đến m và tổng tiền là ít nhất. (N<=30).
Xếp hàng
Có N người cần xếp thành một hàng ngang, biết rằng độ thân thiết của người i và người j là a[i,j]. Hãy tìm cách xếp hàng cho n người trên sao cho hai người liền kề nhau trong hàng phải có độ thân thiết lớn hơn k cho trước ( N < =20).