Как добавить вес в мешок, принимая по 2 элемента за раз в массиве?

Question

Найти общий вес в мешке таким образом, чтобы в каждый раз нам нужно было выбирать только 2 предмета из массива и добавлять в мешок.

Входные данные:

int n = 5;
int w = {1 3 7 5 6};

• Элементы с весом 1 и 3 добавляются → 4 (A).
• Затем добавляются элементы A с весом 5 → 9 (B).
• После этого добавляются элементы с весами 6 и 7 → 13 (C).
• Добавляются последние B и C → 22 * ​​1015 *
• totalweight=4(A)+9(B)+13(C)+22

MyLogic:

int totalweight(int n, int w[]){
   int x = w[0] + w[1];
   int t = x;
   int sum = 0;
   for (int i = 2; i < n; i++)
   {
    sum = sum + t;
    t = w[i] + t;
   }

  return sum;
 }

Мой вывод:

31

Ожидаемый результат:

48

Я добавлю позже.Как мне это исправить?

Answer 1

Перечитав ваш комментарий, я считаю, что это скорее вопрос алгоритма.И если это так, я бы рекомендовал вместо этого использовать подход со структурой данных связанного списка.Представьте ваш массив в виде связанного списка,

1->3->5->6->7

Я отсортировал его в первую очередь потому, что ваша цель - найти наименьшее возможное количество.Затем продолжайте выполнять этот алгоритм ниже, пока в вашем связанном списке не останется только один элемент.

1. Добавьте первые два элемента в свой связанный список

2. Удалите первые два элемента из связанного списка, но отследите эту локальную сумму

3. Добавьте эту локальную сумму к глобальной переменной суммы

4. Сохраните локальную сумму в связанном списке, сохраняя отсортированный список

5. Повторяйте, пока в связанном списке не останется только один элемент

Здесьпример списка после каждой итерации этого алгоритма,

1->3->5->6->7, sum = 0
4->5->6->7, sum = 0 + 4 = 4
6->7->9, sum = 4 + 9 = 13
9->13, sum = 13 + 13 = 26
22, sum = 26 + 22 = 48

Я оставлю кодирование на ваше усмотрение, так как оно может быть довольно сложным, чтобы кодировать связанный список и функцию, чтобы он каждый раз сортировалсяэлемент добавлен.Однако, чтобы начать, вот пример того, как добавить элемент в связанный список:

struct Node 
{ 
    int data; 
    struct Node *next; 
};

void addToTheEnd(Node** head, int value) {
    //adds an element to the end of a linked list
    if(*head == NULL) {
        *head = (struct Node*) malloc(sizeof(struct Node));
        (*head)->data = value;
        (*head)->next = NULL;
    }
    else {
        struct Node* current = *head;
        while(current->next != NULL) {
            current = current->next;
        }
        current->next = (struct Node*) malloc(sizeof(struct Node));
        current->next->data = value;
        current->next->next = NULL;
    }
}