时间戳

首页 > 解决方案 > 需要帮助解决 C 中的 0/1 背包问题，具有最高“价值”解决方案，但最少“重量”相同（最高）“价值”

arrays - 需要帮助解决 C 中的 0/1 背包问题，具有最高“价值”解决方案，但最少“重量”相同（最高）“价值”

问题描述

我已经困惑了两周用 C 编写背包问题。

因为我没有设法让它直接与结构一起工作，所以我用一个额外的数组做了一个解决方案。如果您知道如何直接使用结构，那就太好了！

但主要问题是，当我获得多个具有相同值的解决方案时，我只想获得权重最小的解决方案。

到目前为止我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <stdbool.h>
#include <string.h>

#define TEAMS 5 
#define max_players 20

typedef struct Team
{
    char name [10];
    int players;
    bool Is_Playing;
    int points;
} Team;

struct Team one = { "Ones", 12, true, 18 };
struct Team two = { "Twos", 4, true, 10 };
struct Team three = { "Threes", 5, true, 9 };
struct Team four = { "Fours", 12, true, 22 };
struct Team five = { "Fives", 8, true, 15 };

typedef struct selection_entry
{
    int points;
    int team;
    struct selection_entry *prev;
} selection_entry;

Team *teams[TEAMS] = { &one, &two, &three, &four, &five };

int selection(int players[], const int *selection_points, size_t n,
        int capacity, int **solution)
{
    int i, j;
    selection_entry **table;
    int result;
    selection_entry *head;

    /* Allocate the table */
    table = malloc((n + 1) * sizeof(selection_entry *));
    for (i = 0; i <= n; i++) {
        table[i] = malloc((capacity + 1) * sizeof(selection_entry));
    }

    /* Calculate the points and build chains */
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= capacity; j++) {
            if (i == 0 || j == 0) {
                /* Initialising the first row or column */
                table[i][j].points = 0;
                table[i][j].team = 0;
                table[i][j].prev = NULL;
            }
            else if (players[i - 1] <= j) {
                /* Can add team */
                if (selection_points[i - 1] + table[i - 1][j - players[i - 1]].points
                        > table[i - 1][j].points) {
                    /* Add team */
                    table[i][j].points = selection_points[i - 1] + table[i - 1][j - players[i - 1]].points;
                    table[i][j].team = i - 1;
                    table[i][j].prev = &table[i - 1][j - players[i - 1]];
                }
                else {
                    /* Don't add team */
                    table[i][j].points = table[i - 1][j].points;
                    table[i][j].team = table[i - 1][j].team;
                    table[i][j].prev = table[i - 1][j].prev;
                }
            }
            else {
                /* Don't add team */
                table[i][j].points = table[i - 1][j].points;
                table[i][j].team = table[i - 1][j].team;
                table[i][j].prev = table[i - 1][j].prev;
            }
        }
    }

    /* Read back the solution */
    *solution = calloc(n, sizeof(int));
    for (i = 0, head = &table[n][capacity];
            head->prev != NULL;
            head = head->prev, i++) {
        (*solution)[head->team] = 1;
    }

    result = table[n][capacity].points;
    for (i = 0; i <= n; i++) {
        free(table[i]);
    }
    free(table);
    return result;
}

int GetSelectionArraySize()
{
    int s=0;
    for (int i = 0; i < TEAMS; i++)
    {
        if (teams[i]->Is_Playing)
        {
        s++;
        }
    }
    return s;
}

void main()
{
    int a_size = GetSelectionArraySize();
    int players[a_size];
    int selection_points[a_size];
    int i, j=0;
    for (int i = 0; i < TEAMS; i++)
    {
        if (teams[i]->Is_Playing)
        {
            players[j] = teams[i]->players;
            selection_points[j] = teams[i]->points;
            j++;
        }
    }
    
    const int capacity = max_players;
    const size_t n = sizeof(players) / sizeof(players[0]);
    int *solution;
    int points = selection(players, selection_points, n, capacity, &solution);
    fprintf(stdout, "Value: %d\n", points);
    for (i = 0; i < n; i++)
    {
        if (solution[i])
            {
            fprintf(stdout, "Team %d with %d players and %d points.\n", i, players[i], selection_points[i]);
            }
    }
    free(solution);
}

问题：我不知道为什么它不能正常工作，以及我如何得到它来给我最好的解决方案（最高分但在最大指定玩家数量内的玩家最少）。

子问题：数组解决方法让我很恼火，但我无法让它直接与原始结构数组一起工作......

非常感谢您提前！！！

最亲切的问候！

拉尔夫

标签： arrayscstructknapsack-problem

解决方案

我不会详细介绍您的代码，而是让我们看看问题和类似背包的解决方案。

基本上，您的解决方案的相关属性是value和weight，其中是受约束的，并且如果A 和 B 满足约束weight，则解决方案 A 优于解决方案 B。A.value > B.valueA.value = B.value AND A.weight < B.weight

因此，给定一个潜在项目列表[item1, [others...]]，其中包括 items1 的解决方案是可能的，您需要找到更好的解决方案

subresult1 = solve([others...], weightconstraint - item1.weight)
candidate1 = (subresult1.value + item1.value, subresult1.weight + item1.weight)
candidate2 = solve([others...], weightconstraint)
if (candidate1.value > candidate2.value) return candidate1
if (candidate1.value == candidate2.value && candidate1.weight < candidate2.weight) return candidate1
return candidate2

我希望这个伪代码足够清晰，可以解释要实现的逻辑。

推荐阅读