Đây là chương trình C++ tìm giá trị nhỏ nhất của biểu thức đại số bất kỳ. Biểu thức dạng (x1 + x2 + ... + xa) * (y1 + y2 + ... + yb) và (a + b) số nguyên cho trước. Xét tất cả tổ hợp a số và b số còn lại, tính giá trị để tìm giá trị nhỏ nhất.
Thuật toán
Begin hàm MinValue() : Tham số: a[] = mảng lưu các phần tử. x,y = số nguyên. Thân hàm: 1) Tìm tổng các phần tử mảng. 2) Khởi tạo s=0. 3) Vòng lặp i = 0 đến (x + y)-1 Dịch các số nguyên 25 đơn vị để thành số dương. 4) Khai báo mảng boolean p[i][j] biểu diễn true nếu tổng j đạt được bằng cách chọn i số. 5) Khởi tạo mảng. 6) Vòng lặp i = 0 đến (x + y)-1 xác định nếu p[i][j] true, có thể chọn i số từ (x+y) số để tổng thành j. 7) Khởi tạo min_value=INF. 8) Vòng lặp i = 0 đến (MAX * MAX + 1)-1 kiểm tra nếu tổng cụ thể đạt được bằng cách chọn x số. if (p[x][i]) Lấy tổng thực tế vì đã dịch 25 để tránh chỉ số âm trong mảng. 9) In min_value. End
Ví dụ
#include <bits/stdc++.h> using namespace std; #define INF 1e9 #define MAX 25 int MinValue(int a[], int x, int y) { int s= 0; for (int i = 0; i < (x + y); i++) { s+= a[i]; a[i] += 25; } bool p[MAX+1][MAX * MAX + 1]; //Khởi tạo mảng 01. memset(p, 0, sizeof(p)); p[0][0] = 1; for (int i = 0; i < (x + y); i++) { // k tối đa x vì // biểu thức trái có x số for (int k = min(x, i + 1); k >= 1; k--) { for (int j = 0; j < MAX * MAX + 1; j++) { if (p[k - 1][j]) p[k][j + a[i]] = 1; } } } int min_value = INF; for (int i = 0; i < MAX * MAX + 1; i++) { if (p[x][i]) { int tmp = i - 25 * x; min_value = min(min_value, tmp * (s - tmp)); } } cout << "Minimum Value: " << min_value ; } int main() { int x = 2, y = 2; //nhập x và y. int ar[] = { 7,6,4,3 }; MinValue(ar, x, y); return 0; }Kết quả
Minimum Value: 91