c - 试图找到两个数组的非支配解

Question

我试图在优化问题中找到两个数组的非支配值。

我有两个数组，lost_bars_array 和 prices_array。我想做的是最小化丢失的金条，并最大化价格。我想获得一个名为 no_dominated 的最终数组，其中包含两个数组的非支配值的索引。这很容易理解。让我用一个例子来解释这一点。

我们有两个初始数组:

理论过程是这样的:

1.获取第一个值

2. 获取第二个(索引#1)并查看它是否是比第一个更好的解决方案。这意味着我们必须查看第二个是否有更少的损失柱和更高的价格。事实并非如此，它的酒吧更少，价格也更低，所以我们不能说这是一个更好的解决方案。我们将其保存为可能的解决方案

3. 现在是下一个，索引 #2，这个改进了索引 #1 的解决方案，因为它有更少的损失 brs 和更大的价格。但它并没有改善指数 #0，因为它损失的柱线更少，而且价格也更少。所以我们将索引 #0 和索引 #2 保存为可能的解决方案。

4. 索引 #3 和 #4 有更多丢失的条柱和更少的价格，所以将它们作为可能的解决方案拒绝。

5. 最后，与索引 #0 相比，索引 #5 的损失柱数更少，价格更多，因此，索引 #0 的解被拒绝，最终的非支配值将是索引#2 和索引#5 的那些。

这是我迄今为止尝试过的。

#include <stdio.h>

int main(int argc, char** argv)
{
    int lost_bars_array[] = {15, 10,  8, 15, 17,  9};
    int prices_array[]    = {35, 25, 30, 10, 15, 36};
    int no_dominated[6];
    int cont              = 6;

    for (int actual_pos = 0; actual_pos < cont; actual_pos++)
    { 
        if (actual_pos == 0)
        {
            no_dominated[actual_pos] = actual_pos; 
        } 
        else
        {
            // Here's where I've the problems, I dont know how to handle the arrays
            for (int p = 0; p < actual_pos; p++)
            {
                if (lost_bars_array[p] > lost_bars_array[p + 1] && 
                    prices_array[p] < prices_array[p + 1])
                {
                    no_dominated[p] = p;
                }

            }
        }
    }

    printf("\nThe non-dominated solutions index are: %d");
    for (int i = 0; i < 6; i++)
    {
        printf(" %d ", no_dominated[i]);
    }

    printf("\n");

    return 0;
}

代码应输出索引 2 5 作为解决方案。我希望我正确地解释了这个问题。
感谢任何帮助。提前致谢。

Answer 1

下面的程序可以满足您的需求，但我只是针对您的特定情况对其进行了测试；如果只有一个主导解决方案，或者在其他一些特殊情况下，它很可能会失败。但是你可以从这里开始工作。

两个注意事项:

• 您忘记包含可能的解决方案； bool 值 && 只会保存保证更好的解决方案

• 最后一个双循环有点乱；哈希会更容易(解决方案索引将是哈希)，但我认为这需要 c++ 或额外的库。

代码:

#include <stdio.h>

int main() 
{
    int lost_bars_array[] = {15,10,8,15,17,9};
    int prices_array[] = {35,25,30,10,15,36};
    int no_dominated[6];
    int cont = 6;
    int ndom = 0;

    no_dominated[ndom] = 0;
    ndom++;
    for (int actual_pos = 1; actual_pos < cont; actual_pos++) { 
        int ntmp = ndom;
        for(int p = 0; p < ntmp; p++) {
            if (lost_bars_array[no_dominated[p]] > lost_bars_array[actual_pos] && 
                prices_array[no_dominated[p]] < prices_array[actual_pos]) {
                // Replace with a better solution
                no_dominated[p] = actual_pos;
        } else if (lost_bars_array[no_dominated[p]] > lost_bars_array[actual_pos] ||
               prices_array[no_dominated[p]] < prices_array[actual_pos]) {
                // Save as potential solution
                no_dominated[ndom] = actual_pos;
                ndom++;
            }
        }
    }
    // Remove double solutions
    for (int i = 0; i < ndom; i++) {
        for (int j = i; j < ndom; j++) {
            if (no_dominated[i] == no_dominated[j]) {
                ndom--;
            }
        }
    }
    printf("\nThe non-dominated solutions index are:");
    for(int i = 0; i < ndom; i++)
        printf(" %d ", no_dominated[i]);
    printf("\n");
    return 0;
}