在成本和重量限制内计算最佳可能的元素组合

Question

我正在努力帮助我姐姐完成计算机编程的大学作业(我在爱尔兰相当于高中)。我以前用Python和Java编程过，但很少用C。该项目必须用C完成。

本质上，您会获得许多元素。每件元素都有重量、值(value)和成本。其想法是在重量限制和预算范围内计算元素的最佳可能值(value)。

我写了一段代码，但它不起作用。每次运行时，输出都是随机的数字数组，权重和成本值为零...

我认为问题与 realloc 函数有关，但我可能不知道如何使用它。我本质上是想创建一个可以更改长度的数组。我不认为 realloc 是为此设计的...任何建议或解决方案都会有很大的帮助...

#include <stdio.h>
#include <stdlib.h>

int check(int finalList[], int value, int current,int limit, int weight, int tempw, int budget, int cost, int tempc, int Clist[], int x);

int main()
{
    int nlist[5] = {1,2,3,4,5};
    int values[5] = {4,5,7,2,9};
    int weights[5] = {1,4,8,2,9};
    int costs[5]= {3,6,2,1,8};
    int n = 5;
    int x,i,j,k,l,m,p=0;
    int value=0, cost= 0, weight = 0,tempv=0, tempw = 0, tempc = 0;
    int budget = 45;
    int limit = 12;
    int finalList[n];

    for(x=0;x<n;x++)
    {
        for(i=0;i<n;i++)
        { 
            int list[x+1];
            list[0] = nlist[i];
            tempv = values[i];
            tempw = weights[i];
            tempc = costs[i];

            for(j=0;j<x;j++)
            {
                for(k=0;k<n;k++)
                {
                    list[0]=nlist[i];
                    tempv = values[i];
                    tempw = weights[i];
                    tempc = costs[i];
                    m = p;

                    for(l=0;l<x;l++)
                    {
                        if(m==i)
                        {
                            m++;
                            p++;
                        }

                        list[l] = nlist[m];
                        tempv = tempv + values[m];
                        tempw = tempw + weights[m];
                        tempc = tempc + costs[m];
                        check(finalList, value,tempv, limit, weight, tempw, budget, cost, tempc, list,x);
                    }

                    p++;
                }
            }
            check(finalList, value,tempv,limit, weight, tempw, budget, cost, tempc, list,x);
        }
    }

    printf("\nMost efficient item list:" );
    for(i=0;i<n;i++)
    {
        printf("%d", finalList[i]);
    }
    printf("\nWeight: %d", weight);
    printf("\nCost: %d", cost);
}


int check(int finalList[], int value, int current,int limit, int weight, int tempw, int budget, int cost, int tempc, int Clist[], int x)
{
    if(tempw<=limit)
    {
        if(tempc<=budget)
        {
            if (current>value)
            {
                finalList = realloc(finalList, 1*(x+1));
                finalList= Clist;
                value = current;
                weight = tempw;
                cost = tempc;
            }

        }
    }
    return finalList,value,weight,cost;
}

Answer 1

首先，我将尝试向您展示面向对象的原则以及适当的数据结构和小函数如何帮助使代码更具可读性并使错误更容易发现。

#include <stdio.h>
#include <stdlib.h>

const int MAX_COST = 45;
const int MAX_WEIGHT = 12;

const int VALUES[5] = {4, 5, 7, 2, 9};
const int WEIGHTS[5] = {1, 4, 8, 2, 9};
const int COSTS[5] = {3, 6, 2, 1, 8};

typedef struct
{
    // total over all items in the subset
    int value;
    int weight;
    int cost;

    // subset of items
    int indices[5];
    int num_indices;
} candidate;

void candidate_init (candidate *c)
{
    c->value = 0;
    c->weight = 0;
    c->cost = 0;
    c->num_indices = 0;
}

void candidate_print (const candidate *c)
{
    printf ("items:  ");
    for (int i = 0; i < c->num_indices; i++) {
        printf ("%d, ", c->indices[i]);
    }
    putchar ('\n');

    printf ("value:  %d\n", c->value);
    printf ("weight: %d\n", c->weight);
    printf ("cost:   %d\n", c->cost);
};

void candidate_add_item (candidate *c, int i)
{
    c->value += VALUES[i];
    c->weight += WEIGHTS[i];
    c->cost += COSTS[i];

    c->indices[c->num_indices++] = i;
}

int candidate_is_ok (const candidate *c)
{
    return ((c->weight <= MAX_WEIGHT) && (c->cost <= MAX_COST));
}

您不需要动态分配，因为项目数量在编译时已知。

candidate candidates[32]; // 32 == pow (2, 5)
int num_candidates = 0;

void candidates_insert (candidate *c)
{
    candidates[num_candidates++] = *c;
}

现在是主要代码，应该很容易理解:

int main ()
{
    // insert empty candidate                                                   
    {
        candidate c;
        candidate_init (&c);
        candidates_insert (&c);
    }

    // generate all valid candidates                                            
    for (int i = 0; i < 5; i++) {
        int n = num_candidates;
        for (int j = 0; j < n; j++) {
            candidate c = candidates[j];
            candidate_add_item (&c, i);
            if (candidate_is_ok (&c)) {
                candidates_insert (&c);
            }
        }
    }

    // find candidate with maximum value                                        
    int max_value = 0;
    int max_i = 0;

    for (int i = 0; i < num_candidates; i++) {
        if (candidates[i].value > max_value) {
            max_value = candidates[i].value;
            max_i = i;
        }
    }

    // print solution                                                           
    candidate_print (&candidates[max_i]);
}