}
}
void InPA()
{
int i; i = 1;
while(pa[i])
{
printf("%3d", pa[i]); i++;
}
printf("-%3d", vmax);
Có thể bạn quan tâm!
-
Trọng Lương Và Giá Trị 5 Loại Đồ Vật -
Thiết kế và đánh giá thuật toán - 21 -
Thiết kế và đánh giá thuật toán - 22 -
Thiết kế và đánh giá thuật toán - 24 -
Thiết kế và đánh giá thuật toán - 25
Xem toàn bộ 205 trang tài liệu này.
}
main()
{
DocDL();
QHD();
TruyVet(); InPA();
getch();
}
2. Cài đặt thuật toán quay lui giải bài toán chiếc ba lô
/*Doc du lieu tu file Balo.txt
Dong thu nhat ghi so do vat (n) va trong luong toi da cua ba lo (m) n dong tiep theo ghi trong luong va gia tri cua vat
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define max 100 int n, W;
173
int w[max], v[max], vmax; int daxet[max];
int x[max]; int pa[max]; int vi, wi; void DocDL()
{
FILE *f;
f = fopen("BaLo.txt", "r"); if(!f)
{
puts("Loi mo tep");
}
fscanf(f, "%d", &n);
fscanf(f, "%d", &W); for(int j=0; j<n; j++)
{
fscanf(f, "%d", &w[j]);
fscanf(f, "%d", &v[j]);
}
}
void LuuPa(int i)
{
//intf("%dn", i);
for(int j=0; j<=i; j++) pa[j] = x[j];
}
void InPa()
{
int i = 0; while(pa[i])
174
{
printf("%3d", pa[i]); i++;
}
}
void Try(int i)
{
for(int j=0; j<n; j++)
if(!daxet[j] && (wi+w[j])<=W)
{
x[i] = j+1; daxet[j] = 1; vi += v[j];
wi += w[j]; if(vi>vmax)
{
vmax = vi;
LuuPa(i);
}
Try(i+1);
//x[i] = 0;
daxet[j] = 0; wi -= w[j];
vi -= v[j];
}
}
int main()
{
DocDL();
wi = 0;
vmax = 0;
175
vi = 0; Try(0);
InPa();
getch();
}
3. Cài đặt thuật toán nhánh cận giải bài toán chiếc ba lô
/*Doc du lieu tu file Balo.txt
Dong thu nhat ghi so do vat (n) va trong luong toi da cua ba lo (m) n dong tiep theo ghi trong luong va gia tri cua vat
*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 100
int v[max], w[max]; int daxet[max];
int vi, wi, vmax; int n, W;
int x[max]; int pa[max]; void DocDL()
{
FILE *f;
f = fopen("BaLo.txt", "r"); if(!f)
{
puts("Loi mo tep"); getch();
exit(0);
}
fscanf(f, "%d", &n);
176
fscanf(f, "%d", &W); for(int i=1; i<=n; i++)
{
fscanf(f, "%d", &w[i]);
fscanf(f, "%d", &v[i]);
}
fclose(f);
}
int sumv(int i)
{
int s = 0;
for(int j=i; j<=n; j++) s += v[j];
return s;
}
void LuuPa(int i)
{
for(int j=1; j<=i; j++) pa[j] = x[j];
}
void InPa()
{
int i = 1; while(pa[i])
{
printf("%3d", pa[i]); i++;
}
}
void Try(int i)
{
177
for(int j=1; j<=n; j++)
{
int v1, w1;
v1 = vi + v[j]; w1 = wi + w[j];
if(!daxet[j] && w1<=W) if((sumv(j+1)+v1)>vmax)
{
x[i] = j; daxet[j] = 1; vi = v1;
wi = w1; if(vi>vmax)
{
vmax = vi;
LuuPa(i);
}
Try(i+1); daxet[j] = 0; vi -= v[j];
wi -= w[j];
}
}
}
int main()
{
DocDL();
vi = 0;
wi = 0;
vmax = 0; Try(1);
178
InPa();
getch();
}
4. Cài đặt thuật toán quy hoạch động giải bài toán dãy con chung dài nhất
Input: Hai dãy d1, d2
Output: Dãy con chung có độ dài lớn nhất
/* Đọc dữ liệu từ file DayConChung.txt: mỗi dòng ghi 1 dãy*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define max 100 char a[max], b[max]; int n, m;
int L[max][max]; char c[max]; void DocDL()
{
FILE *f;
f = fopen("DayConChung.txt", "r"); if(!f)
{
puts("Loi mo tep"); getch();
exit(0);
}
char s[max]; int i;
fgets(s, 100, f); n = strlen(s);
179
s[n-1]=' ';
a[0] = ' ';
strcat(a, s);
fgets(s, 100, f); m = strlen(s); s[m-1]=' ';
b[0] = ' ';
strcat(b, s);
}
int Max(int a, int b, int c)
{
if(a>=b && a>=c) return a;
if(b>=a && b>=c) return b;
return c;
}
void QHD()
{
int i, j;
for(i=1; i<=n; i++) for(j=1; j<=m; j++)
if(a[i] == b[j])
L[i][j] = Max(L[i-1][j], L[i][j-1], L[i-1][j-1] + 1);
else
L[i][j] = Max(L[i-1][j], L[i][j-1], L[i-1][j-1]);
}
void TruyVet()
{
int i, j;
i=n-1; j=m-1;
180