Tối đa hóa giá trị x + y + z sao cho ax + by + cz = n trong C++

Chúng ta được cho các số nguyên a, b, c, n. Mục tiêu là tối đa hóa tổng của x, y và z sao cho ax + by + cz = n.

Từ công thức trên:

cz = n - (ax + by)
z = (n - (ax + by)) / c

Bằng cách cố định x và y, tính z bằng công thức trên, với mỗi x, y, z. Tính tổng và lưu tổng tối đa thu được.

Ví dụ

Đầu vào

n = 6, a = 3, b = 4, c = 5;

Đầu ra

tối đa x+y+z là 2.

Giải thích − với x=2, y=0, z=0 thì ax+by+cz=n.

3*2 + 0*4 + 0*5 = 6 = n

Đầu vào

n = 4, a = 3, b = 1, c = 2;

Đầu ra

tối đa x+y+z = 4

Giải thích − với x=0, y=4, z=0 thì ax+by+cz=n.

0*3 + 4*1 + 0*2 = 4 = n

Phương pháp sử dụng trong chương trình dưới đây

• Số nguyên a, b, c, n dùng cho biểu thức ax + by + cz = n.
• Hàm maximize(int n, int a, int b, int c) nhận a, b, c, n và trả về tổng tối đa có thể của x, y, z sao cho ax + by + cz = n.
• Lấy tất cả giá trị ax có thể, for(i=0; i<=n; i+=a), cũng
• Lấy tất cả giá trị by có thể for(j=0; j<=n; j+=b),
• Tính z = (n - (ax + by)) / c.
• Bây giờ x = i/a và y = j/b. Tính x + y + z và lưu vào temp.
• Nếu temp >= maxx cho đến nay, cập nhật maxx.
• Trả về maxx là tổng mong muốn.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

int maximize(int n, int a, int b, int c) { 
    int maxx = 0; 
    // i cho các giá trị có thể của ax
    for (int i = 0; i <= n; i += a) 
        // j cho các giá trị có thể của by
        for (int j = 0; j <= n - i; j += b) { 
            float z = (n - (i + j)) / c; 
            // Nếu z là số nguyên
            if (floor(z) == ceil(z)) { 
                int x = i / a; 
                int y = j / b; 
                int temp = x + y + z; 
                if (temp >= maxx) 
                    maxx = temp; 
            } 
        } 
    return maxx; 
} 

int main() { 
    int n = 6, a = 3, b = 4, c = 5; 
    cout << "Tối đa hóa giá trị x + y + z: " << maximize(n, a, b, c); 
    return 0; 
}

Kết quả

Tối đa hóa giá trị x + y + z: 2