 # Đề tài: Thuật toán của bài toán cái túi và người du lịch

1. ## Thuật toán của bài toán cái túi và người du lịch

Xin các bác cho em biết về thuật toán của bài toán cái túi và người du lịch, em ko hiểu gì về hai bài này cả.  2. thuật toán là thuật toán nào ? 2 bài này có nhiều cách giải lắm hix hix ! hỏi thế sao mình biết được ! 3.  Thành viên mới Ngày gia nhập
09 2007
Bài viết
17
chậc mấy bài toán này hay lém, đọc bài này nhớ lão hdkinhcan quá , he he sao ko thấy lão vào thảo luận mấy bài này nữa nhỉ ? 4. Đây ko phải là thuật toán mà chỉ có thể gọi nó là thuật giải mà thôi, tên của bài toán chính xác là knapsack, các bạn có thể search google để tìm hiểu (nếu biết đọc tiếng Anh). Đây là 1 bài toán nằm trong các bài toán về Quy hoạch động 5.  Thành viên mới Ngày gia nhập
11 2007
Bài viết
9
bạn nào có code viết trên C không vậy ? cho mình tham khảo với ^^
code bài cái túi ai xem giúp mình cái,mình chạy nó k đc như ý muốn,khó hiểu lắm í
Code:
```#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<dos.h>
#define TRUE 1
#define FALSE 0
#define MAX 100
int x[MAX],xopt[MAX];
float fopt,cost,weight;
void Init(float *C,float *A,int *n,float *w)
{ int i;
FILE *fp;
fopt=0;weight=0;
fp=fopen("caitui.in","r");
if(fp==NULL)
{ printf("\nKhong co tep input");
delay(5000);return;
}
fscanf(fp,"%d%f",n,w);
for(i=1;i<=*n;i++) xopt[i]=0;
printf("\nSo luong do vat%d:",*n);
printf("\nGioi han tui %8.2f:",*w);
printf("\nVector gia tri:");
for(i=1;i<=*n;i++)
{
fscanf(fp,"%f",&C[i]);
printf("%8.2f",A[i]);
}
printf("\nVEctor trong luong:");
for(i=1;i<=*n;i++)
{ fscanf(fp,"%f",&A[i]);
printf("%8.2f",A[i]);
}
fclose(fp);

}
void swap(int n)
{
int i;
for(i=1;i<=n;i++)
xopt[i]=x[i];
}
void Update_Kyluc(int n)
{
if(cost>fopt)
{
swap(n);
fopt=cost;
}
}
void Try(float *A,float *C,int n,float w,int i)
{
int j,t=(w-weight)/A[i];
for(j=t;j>=0;j--)
{
x[i]=j;
cost=cost+C[i]*x[i];
weight=weight+x[i]*A[i];
if(i==n)
Update_Kyluc(n);
else if(cost+C[i+1]*(w-weight)/A[i+1]>fopt)
{
Try(A,C,n,w,i+1);
}
weight=weight-A[i]*x[i];
cost=cost-C[i]*x[i];
}
}
void Result(int n)
{ int i;
printf("\nGia tri do vat %8.2f",fopt);
printf("\nPhuong an toi uu:");
for(i=1;i<=n;i++)
printf("%3d",xopt[i]);
}
void main(void)
{ int n;
float A[MAX],C[MAX],w;
clrscr();
Init(C,A,&n,&w);
Try(C,A,n,w,1);
Result(n);
getch();
}``` 6. ## Thuật toán của bài toán cái túi và người du lịch

Bài này thực ra có 2 phiên bản :
- Phiên bản 1 : là số đồ chọn là số nguyên.
ví dụ :
có 3 món đồ với dung lượng túi là 10
+ món 1 : nặng 4 , giá trị 10
+ món 2 : nặng 6 , giá trị 10
+ món 3 : nặng 10, giá trị 21
Vì giá trị nguyên, nên dễ thấy ta phải chọn món thứ 3 để có giá trị là lớn nhất
- Phiên bản 2 : là tên trộm có thể cắt món đồ ra để được giá trị lớn nhất , cũng với ví dụ trên ta có giá trị 1 phần của từng món như sau :
10 / 4 = 2.5
10 / 6 = 1.666667
21 / 10 = 2.1
Tức là nếu theo cách này thì ta sẽ chọn món thứ nhất 4kg + 6kg ( của món thứ 3 ) thì sẽ được giá trị lớn nhất.
Code của bạn mình nghĩ là giải theo phương pháp tham lam nhưng cách đặt tên biến i,j.. nên đọc vào mệt lắm. Code này mình viết theo 2 phương pháp, mình giải phiên bản 1 bằng quy hoạch động và phiên bản 2 bằng tham lam :
-Giải thuật cho phương pháp tham lam rất đơn giản : sắp xếp lại các tỉ số giá trị ( cái mình vừa ví dụ ) sau đó thử sai là xong .
-Giải thuật cho QHD cũng đơn giản như sau :
F[i][j] là giá trị lớn nhất có thể đạt được bao gồm i món đồ và giới hạn trọng lượng là j
thì ta có :
Không lấy món đồ đó thì thứ i thì : F[i][j] = F[i-1][j]
Ngược lại nếu chọn món đồ thứ i + điều kiện [được giá trị lớn hơn] thì
F[i][j] = F[i-1][j-khối lượng[i]] + giá trị[i]
Ta chỉ cần tính cho tới F[món đồ][giá tiền] nhập vào là xong
Đây là code , có chỗ nào không hiểu thì mình sẽ giải thích :
C++ Code:
1. #include <iostream>
2. #include <iomanip>
3. #include <fstream>
4. #include <algorithm> //sort function
5.
6. using namespace std;
7.
8.
9. class Knapstack
10. {
11.     public :
12.
13.         Knapstack(int number_of_items, int weight_of_bag);
14.        ~Knapstack();
15.
16.         //Copy constructor
17.         Knapstack::Knapstack(Knapstack &copy_object);
19.         const Knapstack &operator = (Knapstack &);
20.
21.         /*method for greedy*/
22.         void Solving_by_greedy();
23.         void Sort_items();
24.
25.         /*method for dynamic programming*/
26.         void Solving_by_dynamic_programming();
27.         void Dynamic_programming_trace_solution();
28.
29.         friend istream &operator >> (istream &, Knapstack &);
30.
31.     private :
32.
33.         int weight_of_bag;
34.         int number_of_items;
35.
36.        //data information
37.         int *items_No;
38.         int *items_value;
39.         int *items_weight;
40.         //solution array
41.         float *greedy_solution;
42.         int **dynamic_solution;
43. };
44.
45.
46. Knapstack::Knapstack(int number_of_items, int weight_of_bag)
47.     :number_of_items(number_of_items), weight_of_bag(weight_of_bag)
48. {
49.     greedy_solution = new float[number_of_items+1];
50.     items_No = new int[number_of_items+1];
51.     items_value = new int[number_of_items+1];
52.     items_weight = new int[number_of_items+1];
53.
54.
55.     dynamic_solution = new int *[number_of_items+1];
56.     for(int x = 0; x <= number_of_items; x++)
57.     {
58.         dynamic_solution[x] = new int[weight_of_bag+1];
59.     }
60.
61.     for(int x = 0; x <= number_of_items; x++)
62.     {
63.         *(items_No + x) = x;
64.         *(items_value + x) = 0;
65.         *(items_weight + x) = 0;
66.         *(greedy_solution + x) = 0.0;
67.     }
68.
69.     for(int x = 0; x <= number_of_items; x++){
70.         for(int y = 0; y <= weight_of_bag; y++){
71.             dynamic_solution[x][y] = 0;
72.         }
73.     }
74. }
75.
76.
77. //Destructor
78.  Knapstack::~Knapstack()
79. {
80.     delete[] items_No;
81.     delete[] items_value;
82.     delete[] items_weight;
83.
84.     delete[] greedy_solution;
85.     for(int x = 0; x <= number_of_items; x++){
86.         delete[] dynamic_solution[x];
87.     }
88.     delete[] dynamic_solution;
89. }
90.
91.
92. //Copy constructor
93. Knapstack::Knapstack(Knapstack &copy_object)
94.     :number_of_items(copy_object.number_of_items), weight_of_bag(copy_object.weight_of_bag)
95. {
96.     //For array of greedy algorithm
97.     greedy_solution = new float[number_of_items+1];
98.     items_No = new int[number_of_items+1];
99.     items_value = new int[number_of_items+1];
100.     items_weight = new int[number_of_items+1];
101.
102.     for(int x = 0; x <= number_of_items; x++)
103.     {
104.         *(items_No + x) = copy_object.items_No[x];
105.         *(items_value + x) = copy_object.items_value[x];
106.         *(items_weight + x) = copy_object.items_weight[x];
107.         *(greedy_solution + x) = copy_object.greedy_solution[x];
108.     }
109.
110.     //For array of dynamic programming algorithm
111.     dynamic_solution = new int *[number_of_items+1];
112.     for(int x = 0; x <= number_of_items; x++)
113.     {
114.         dynamic_solution[x] = new int[weight_of_bag+1];
115.     }
116.
117.     for (int x = 0; x <= number_of_items; x++)
118.     {
119.         for (int y = 0; y <= weight_of_bag; y++)
120.         {
121.             dynamic_solution[x][y] = copy_object.dynamic_solution[x][y];
122.         }
123.     }
124. }
125.
126.
127. const Knapstack &Knapstack::operator = (Knapstack &obj)
128. {
129.     if (&obj != this) //check for self-assignment
130.     {
131.         //deallocate new left-side of array
132.         if((number_of_items != obj.number_of_items) || (weight_of_bag != obj.weight_of_bag))
133.         {
134.             //Reclaim space
135.             delete[] items_No;
136.             delete[] items_value;
137.             delete[] items_weight;
138.             delete[] greedy_solution;
139.
140.             for( int x = 0; x <= number_of_items; x++){
141.                 delete[] dynamic_solution[x];
142.             }
143.             delete[] dynamic_solution;
144.             /*----END RECLAIM SPACE----*/
145.
146.             //Resize object.
147.             number_of_items = obj.number_of_items;
148.             weight_of_bag = obj.weight_of_bag;
149.
150.             //Create space for array copy
151.             dynamic_solution = new int*[number_of_items+1];
152.             for(int x = 0; x <= number_of_items; x++)
153.             {
154.                 dynamic_solution[x] = new int[weight_of_bag+1];
155.             }
156.
157.
158.             items_No = new int[number_of_items+1];
159.             items_value = new int[number_of_items+1];
160.             items_weight = new int[number_of_items+1];
161.             greedy_solution = new float[number_of_items+1];
162.             /*----END CREATE SPACE----*/
163.
164.             //copy all arrays into object
165.             for(int x = 0; x <= number_of_items; x++)
166.             {
167.                 *(items_No + x) = obj.items_No[x];
168.                 *(items_value + x) = obj.items_value[x];
169.                 *(items_weight + x) = obj.items_weight[x];
170.                 *(greedy_solution + x) = obj.greedy_solution[x];
171.             }
172.
173.             for (int x = 0; x <= number_of_items; x++)
174.             {
175.                 for (int y = 0; y <= weight_of_bag; y++)
176.                 {
177.                     dynamic_solution[x][y] = obj.dynamic_solution[x][y];
178.                 }
179.             }
180.         }
181.     }
182.     return *this; //reference return
183. }
184.
185.
186. istream &operator >> (istream &input, Knapstack &obj)
187. {
188.     cout << "\n### Data Information      ###\n";
189.     cout << "\nThe number of items : ";
190.     input >> obj.number_of_items;
191.     cout << "\nThe maximum capacity of bags: ";
192.     input >> obj.weight_of_bag;
193.
194.     for(int i = 1; i <= obj.number_of_items; i++)
195.     {
196.         cout << " The  [" << i << "] item weigh : ";
197.         input >> obj.items_weight[i];
198.         cout << " Its value is  :  ";
199.         input >> obj.items_value[i];
200.         cout << endl;
201.     }
202.
203.     return input;
204. }
205.
206.
207. void Knapstack::Sort_items()
208. {
209.    for(int x = number_of_items; x >= 2; x--)
210.     {
211.         for(int y = 1; y <= number_of_items - x; y++)
212.         {
213.             if(((float)items_value[y]/items_weight[y]) > ((float)items_value[y-1]/items_weight[y-1]))
214.             {
215.                 swap(items_weight[y], items_weight[y-1]);
216.                 swap(items_value[y], items_value[y-1]);
217.                 swap(items_No[y], items_No[y-1]);
218.             }
219.         }
220.     }
221. }
222.
223.
224. void Knapstack::Solving_by_greedy()
225. {
226.     int _the;//the item
227.     float max_profit = 0.0;
228.
229.     Sort_items();
230.
231.     for(_the = 1; _the < number_of_items; _the++)
232.     {
233.         if(items_weight[_the] > weight_of_bag)
234.             break;
235.
236.         greedy_solution[_the] = 1.0;
237.
238.         weight_of_bag = weight_of_bag - items_weight[_the];
239.         max_profit += items_value[_the];
240.
241.         cout << "\n Items chosen : "<< items_No[_the]
242.              << "\nwith the % quantiy %:" << greedy_solution[_the] << endl;
243.
244.     }
245.
246.
247.     if(_the <= number_of_items)
248.     {
249.         greedy_solution[_the] = (float)weight_of_bag/items_weight[_the];
250.         cout << "\n" << items_No[_the] << "\nwith the quantiy % chosen : " << greedy_solution[_the] << endl;
251.         max_profit = max_profit + (greedy_solution[_the]*items_value[_the]);
252.     }
253.     cout << "\n Maximum value the thief can get : " << max_profit;
254. }
255.
256.
257. void Knapstack::Solving_by_dynamic_programming()
258. {
259.     for (int x = 1; x <= number_of_items; x++)
260.     {
261.         for (int y = 0; y <= weight_of_bag; y++)
262.         {
263.             dynamic_solution[x][y] = dynamic_solution[x-1][y];
264.             if (y >= items_weight[x] && dynamic_solution[x][y] < dynamic_solution[x-1][y-items_weight[x]] + items_value[x] && (y-items_weight[x]) >= 0)
265.             {
266.                 dynamic_solution[x][y] = dynamic_solution[x-1][y-items_weight[x]] + items_value[x];
267.             }
268.         }
269.     }
270. }
271.
272. void Knapstack::Dynamic_programming_trace_solution()
273. {
274.     cout << "Maximum value the thief can get : "
275.          << dynamic_solution[number_of_items][weight_of_bag] << endl;
276.
277.     while (number_of_items != 0)
278.     {
279.         if(dynamic_solution[number_of_items][weight_of_bag] != dynamic_solution[number_of_items-1][weight_of_bag])
280.         {
281.             cout << "Chosen items are : " << number_of_items;
282.             weight_of_bag = weight_of_bag - items_weight[number_of_items];
283.         }
284.         number_of_items--;
285.     }
286. }
287.
289. {
290.     Knapstack problem(10,10);
291.     cin >> problem;
292.
293.     int command;
294.     cout << "Enter a method for solving knapstack problems :\n\n"
295.          << "\n.Greedy\n"
296.          << "\n.Dynamic programming\n" << endl;
297.     cin >> command;
298.
299.
300.     if (command == 1)
301.     {
302.         problem.Solving_by_greedy();
303.     }
304.     else
305.     {
306.         problem.Solving_by_dynamic_programming();
307.         problem.Dynamic_programming_trace_solution();
308.     }
309. }
310.
311. int main()
312. {
314.     system("pause");
315.     return 0;
316. }
Đã được chỉnh sửa lần cuối bởi rox_rook : 02-03-2008 lúc 05:17 AM. 7.  Thành viên mới Ngày gia nhập
11 2007
Bài viết
9
lúc mình chạy í,nhập y như ví dụ của bạn,đến khi chọn 1,greedy thì k chạy đc,chọn dynamic thì ok...thanks bạn nhiều nha ^^ 8. Hic, sorry bạn nha ! Do lúc đầu bug tại thằng dynamic, chăm chú vào nó mà quên khởi tạo cho mãng Items_No[]. Bạn sữa lại ở constructor :
PHP Code:
``` for(int x = 0; x <= number_of_items; x++)     {         *(items_No + x) = x+1;//fixed         *(items_value + x) = 0;         *(items_weight + x) = 0;         *(greedy_solution + x) = 0.0;     } [/quote]  ``` 9.  Thành viên mới Ngày gia nhập
11 2007
Bài viết
9
bạn ơi bạn tách riêng cho mình chỉ có quy hoạch động đc k ?
thanks bạn nhiều lắm í ^^ 10. Giải thuật mình đã trình bày, code mình cũng chú thích ghi ra rõ ràng 2 phần, hơn nữa mình đặt tên biến và hàm hầu như phản ánh toàn nội dung của nó rồi còn gì ? Bạn không chịu đọc mà bắt mình code thì chắc chắn câu trả lời của mình sẽ là không !! Nếu bạn còn vướng mắt hoặc bạn code còn sai thì post lên đây mình sẽ giúp ! Còn code cho bạn chắc chắn mình không làm ! Thân !  #### Quyền hạn của bạn

• Bạn không thể gửi đề tài mới
• Bạn không thể gửi bài trả lời
• Bạn không thể gửi các đính kèm
• Bạn không thể chỉnh sửa bài viết của bạn