多个参数的影响下怎么求最优解

SLCoCo

比如X+Y+Z=10,求X*Y^Z的最大值
这种类似的问题该怎么求解。请大佬指条明路

RainPPR

学过最大抑或对，用Trie字典树做的，感觉有点像，你看看我的笔记：

最大异或对

暴力

1. 第一重循环：枚举第一个数
   1. 第二重循环：枚举第二个数
      1. 异或运算，取最大值
2. 输出最大值

优化

思路：第二重循环，是寻找所有数字里，与这一个数异或，结果最大的数

如何找出来这个数？

• 每一个数，都可以看成一个 31 位的二进制串

• 下一个数的最高位与这个数的最高位不同的，与这个数异或的结果，一定更大

• 每一步都走与这个数这一位不同的分支，如果只有一个分支，就 $\texttt{OVER}$

• 走到叶结点时，就是与这个数异或结果最大的数了。

代码

#include<cstdio>
#include<iostream>

using namespace std;

const int N = 1e5 + 10, M = 31 * N;

int n, idx;
int a[N];
int son[M][2];

void insert(int x)
{
    int p = 0;
    for (int i = 30 ; i >= 0 ; --i)
    {
        int u = x >> i & 1;
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30 ; i >= 0 ; --i)
    {
        int u = x >> i & 1;
        if (son[p][!u])
            p = son[p][!u], res = (res << 1) + !u;
        else
            p = son[p][u], res = (res << 1) + u;
    }
    return res;
}

int main()
{
    scanf("%d", &n);

    int res = 0;
    for (int i = 0 ; i < n ; ++i)
    {
        scanf("%d", a + i);
        insert(a[i]);   // 先插入再查询，减少判断
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }

    printf("%d\n", res);
    return 0;
}

SLCoCo

RainPPR 发表于 2022-12-15 18:47
学过最大抑或对，用Trie字典树做的，感觉有点像，你看看我的笔记：
[md]# 最大异或对

我是想着有没有不用枚举的方法

SLCoCo

结衣酱 发表于 2022-12-15 18:53
我感觉这种求解是不是多元函数微分学的条件极值里面的内容。

你这么一说好像是这么一回事。。。不过高数都忘光了

alan-blues

有一门“最优化方法”可以看下。有约束的优化

gzsklsskszngc

如果X+Y+Z=10，那么一种可能的方法求XY^Z的最大值是，对于所有的X、Y、Z的可能取值，计算出XY^Z的值，然后比较它们，取最大值。不过，这种方法并不一定能得到最优解。

在求解最优解时，通常需要考虑多个因素的影响，比如约束条件、目标函数的形式等。根据不同的情况，可以采用不同的方法来求解。例如，对于线性规划问题，可以使用线性规划算法求解；对于凸优化问题，可以使用梯度下降法求解等。

cloud2010

x,y,z都是正数,否则xyz无最大值

x^3+y^3+z^3 >= 3xyz
x+y+z >= 3 * 3次根号xyz

xyz <= ((x+y+z)/3)^3 = (10/3)^3

SLCoCo

cloud2010 发表于 2022-12-15 21:03
x,y,z都是正数,否则xyz无最大值

x^3+y^3+z^3 >= 3xyz

我这个只是举个例子。实际上计算式挺复杂的。其次后面是y的z次方不是xyz相乘。不过还是谢谢了

cloud2010

SLCoCo 发表于 2022-12-15 23:21
我这个只是举个例子。实际上计算式挺复杂的。其次后面是y的z次方不是xyz相乘。不过还是谢谢了

老眼昏花