c - 如何通过一次在数组中取出 2 个项目来将权重添加到 sack 中？

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
• 总重量=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;
    }
}