โปรแกรม C++ หาค่าสูงสุดของนิพจน์พีชคณิต

การหาค่าสูงสุดของนิพจน์พีชคณิต

นี่คือโปรแกรม C++ หาค่าสูงสุดของนิพจน์พีชคณิตรูปแบบ (x1 + x2 + ... + xa) * (y1 + y2 + ... + yb) โดยมีจำนวนเต็ม (a + b) ตัว พิจารณาการจัดหมู่ทั้งหมดของ a ตัวและ b ตัวที่เหลือ คำนวณค่าแล้วหาค่าสูงสุด

อัลกอริทึม

Begin
    ฟังก์ชัน MaxValue():
    พารามิเตอร์: a[] = อาเรย์เก็บสมาชิก, x, y = จำนวนเต็ม
    1) หาผลรวมของอาเรย์
    2) เริ่มต้น s = 0
    3) วนลูป i = 0 ถึง (x+y-1) เลข shift 25 เพื่อให้เป็นบวก
    4) ประกาศอาเรย์ boolean p[i][j] แทนว่า sum j ถึงได้โดยเลือก i ตัว
    5) เริ่มต้นอาเรย์
    6) วนลูป i = 0 ถึง (x+y)-1 ถ้า p[i][j] จริง แสดงว่าเลือก i ตัวจาก (x+y) ได้ผลรวม j
    7) เริ่มต้น max_value = -INF
    8) วนลูป i = 0 ถึง (MAX*MAX+1)-1 ถ้า p[x][i] จริง
       หาผลรวมจริง (เพราะ shift 25) คำนวณ max_value = max(max_value, tmp * (s - tmp))
    9) แสดง max_value
End

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 25

int MaxValue(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];
    memset(p, 0, sizeof(p));
    p[0][0] = 1;
    for (int i = 0; i < (x + y); i++) {
        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 max_value = -INF;
    for (int i = 0; i < MAX * MAX + 1; i++) {
        if (p[x][i]) {
            int tmp = i - 25 * x;
            max_value = max(max_value, tmp * (s - tmp));
        }
    }
    cout << "Maximum Value: " << max_value;
}

int main() {
    int x = 2, y = 2;
    int ar[] = {7, 6, 4, 3};
    MaxValue(ar, x, y);
    return 0;
}

ผลลัพธ์

Maximum Value: 100