Tìm hiểu một vài thuật toán(Phần I)

Bài toán : Hãy sử dụng thuật toán đệ quy viết chương trình tìm X = (x1, x2,.., xn) và f(X) đạt giá trị lớn nhất

Thuật toán giải :

Input:

• X=(x1,x2,…,xn ) là biến toàn cục
• wt=(wt1 ,wt2,…,wtn) là biến toàn cục trọng lượng của từng đồ vật đưa vào
• val=(val1 ,val2,…,valn) là biến toàn cục giá trị của từng đồ vật đưa vào
• n là biến toàn cục số lượng đồ vật đưa vào
• W là biến toàn cục trọng lượng lớn nhất mà túi có thể chứa Output:
• maxvalue giá trị lớn nhất mà túi đó chứa thỏa mãn aixi<W (D)
• X int Max(int a, int b){//lay gia tri lon nhat cua a & b return a > b ? a : b; } int Recursive(int i, int weight){ if (i == 0 || weight == 0) return 0; if (wt[i] > weight) { //danh dau tui co trong luong lon hon trong luong hien thoi X[i] = 1; return Recursive(i - 1, weight); (1) } else { return Max(Recursive(i - 1, weight), Recursive(i - 1, weight - wt[i]) + val[i]); (2) } } Actions: X = (0,0,0,0);// xâu nhị phân ban đầu wt[i] = wt_input;// trọng lượng đồ vật thứ i với i = 1, 2, …. n phần tử nhập vào val[i] = val_input;// giá trị đồ vật thứ i với i = 1, 2, …. n phần tử nhập vào
  i = n (số lượng đồ vật) weight = W (trọng lượng lớn nhất túi có thể mang được) Recursive

• Nếu số lượng đồ vật hoặc trọng lượng hiện thời = 0 thì dừng đệ quy
• Nếu trọng lượng đồ vật thứ i > trọng lượng hiện thời thì: Đánh dấu đồ vật hiện thời Đệ quy với đồ vật thứ i – 1 và trọng lượng hiện thời
• Nếu không thì Tìm giá trị lớn nhất giữa Đệ quy với đồ vật thứ i – 1 và trọng lượng hiện thời Giá trị đồ vật thứ i + Đệ quy với đồ vật thứ i – 1 và (trọng lượng hiện thời – trọng lượng đồ vật thứ i) In ra kết quả EndActions

Kiểm nghiệm thuật toán

Ví dụ với n=4; W= 8; wt1 = 5,val1 = 10; wt2 = 3,val2 = 5; wt3 = 2,val3 = 3; wt4 = 4,val4 = 6 ta có kết quả như sau: I = 4 => weight[i] = 4; weight = 8; wt[i] = 4 > 8 = false; val[i] = 6 I-1 = 3 ; weight = weight - wt[i] = 8 – 4 = 4; wt[i] =2>4 = false; val[i]= 3 I-1=2; weight = weight - wt[i] = 4 – 2 = 2; wt[i]=3>2 = true => X[2] = 1 I-1=1;weight =2 ; wt[i] = 5 > 2 => true => X[1] = 1 I-1=0; return 0; => current value = 6 + 3 = 9; I=2; weight = 4; wt[i] = 3 > 4 = false; val[i]=5 I-1=1;weight=weight-w[i]=4-3=1; wt[i]=5>1= true=>X[1]=1 I-1=0; return 0; => current value = 5 I=1;weight=4;wt[i]=5>4=true=>X[1]=1 I-1=0; return 0; => current value = 5; I=3;weight=8; wt[i]=2>8=false; val[i]=3 I-1=1; weight = weight - wt[i] = 6 – 3 = 3; wt[i]=5>3 = true=>X[1]=1 I-1=0; return 0; => current value = 5 + 3 = 8; I=1;weight =6; wt[i] = 5>6=false;val[i]=10 I-1=0; return 0; => current value = 10; I=2;weight=8; wt[i]=3>8= false;val[i]=5 I-1=1; weight = weight - wt[i] = 8 – 3 = 5; wt[i]=5>5 = false;val[i]=10 I-1=0; return 0; => current value = 5 + 10 = 15; I=1; weight=8; wt[i]=5>8=false;val[i]=10 I-1=0; return 0; => current value = 10;

Cài đặt thuật toán

#include <iostream> #include <fstream> #define MAX 100 int X[MAX], wt[MAX], val[MAX], n, W, maxvalue = -1; using namespace std; void Init(){ ifstream file("data.txt", ios::in); file >> n >> W; for (int i = 1; i <= n; i++){ X[i] = 0; file >> wt[i]; file >> val[i]; } } int Max(int a, int b){//lay gia tri lon nhat cua a & b return a > b ? a : b; } int Recursive_Base(int i, int weight){ if (i == 0 || weight == 0) return 0; if (wt[i] > weight) { //danh dau tui co trong luong lon hon trong luong hien thoi X[i] = 1; return Recursive_Base(i - 1, weight); } else { return Max(Recursive_Base(i - 1, weight), Recursive_Base (i - 1, weight - wt[i]) + val[i]); } } void Print(){ ofstream file("ketqua_thuattoandequy.out", ios::out); file << maxvalue << " "; for (int i = 1; i <= n; i++){ file << X[i] << " "; } file << endl; } void Run(){ Init(); maxvalue = Recursive_Base(n, W); Print(); } int main() { Run(); return 1; }