이것은 모든 대수식의 최소값을 찾는 C++ 프로그램입니다. (x1 + x2 + x3 + . . . + xa) * (y1 + y2 + . . . + yb) 및 (a + b) 형식의 대수식 ) 정수가 주어집니다. 숫자와 나머지 b 숫자의 가능한 모든 조합을 고려하고 최소값을 도출할 수 있는 값을 계산합니다.
알고리즘
Begin function MaxValue() : Arguments: a[] = array which store the elements. x,y = integers. Body of the function: 1) Find the sum of array elements. 2) Initialize s=0. 3) Make for loop i = 0 to (x + y)-1 Shift the integers by 25 so that they become positive. 4) Declare a boolean array p[i][j] that represents true if sum j can be reachable by choosing i numbers. 5) Initialization of the array. 6) Make for loop i = 0 to (x + y)-1 to determine If p[i][j] is true, that means it is possible to select i numbers from (x + y) numbers to sum upto j. 7) Initialize min_value=INF. 8) Make for loop i = 0 to (MAX * MAX + 1)-1 to Check if a particular sum can be reachable by choosing x numbers. if (p[x][i]) Get the actual sum as we shifted the numbers by 25 to avoid negative indexing in array . 9) Print the min_value. End
예시
#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]; //Initialize the array to 01. memset(p, 0, sizeof(p)); p[0][0] = 1; for (int i = 0; i < (x + y); i++) { // k can be at max x because the // left expression has x numbers 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; //input is taken of x and y. int ar[] = { 7,6,4,3 }; MinValue(ar, x, y); return 0; }
출력
Minimum Value: 91