0-1背包使用动态规划实现

Question

对于权重、值、max_weight 和 total_items 的给定值，它工作正常，但是当我更改权重、值和其他变量时，它会出现分段错误。

我检查过，当我更改变量时，背包函数 items->value 和 items->weight 变为 NULL。

而items->max_weight和items->total_items变成了0。

我不知道我的代码有什么问题，请帮忙，在此先感谢。

代码

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

typedef struct
{
    int total_items, max_weight;
    int *weight, *value;
} Items_knapsack;


void knapsack(Items_knapsack *items, int solution[][items->max_weight + 1]);
int max(int a, int b);

int main (int argc, char *argv[])
{
    int max_weight = 7, total_items = 4;
    int weight[] = {0, 1, 3, 4, 5};
    int value[] = {0, 1, 4, 5, 7};

    Items_knapsack items = {.value = value, .weight = weight, .max_weight = max_weight, .total_items = total_items};
    int solution[total_items + 1][max_weight + 1];

    knapsack(&items, solution);

    for ( int i = 0; i < total_items + 1; i += 1 )
    {
        for ( int j = 0; j < max_weight + 1; j += 1 )
        {
            printf("%d ", solution[i][j]);
        }

        printf("\n");
    }

    return 0;

}

void knapsack(Items_knapsack *items, int solution[][items->max_weight + 1])
{
    int total_items = items->total_items;
    int max_weight = items->max_weight;

    for ( int *i = (int *) solution; i < &solution[total_items + 1][(max_weight + 1)]; i += 1 )
    {
        *i = 0;
    }

    for ( int i = 1; i < total_items + 1; i += 1 )
    {
        for ( int j = 1; j < max_weight + 1; j += 1 )
        {
            int w = *(items->weight + i); //weight of current item
            int v = *(items->value + i); //value of current item

            if ( w > j )
            {
                solution[i][j] = solution[i - 1][j];
            }

            else
            {
                solution[i][j] = max(v + solution[i - 1][j - w], solution[i - 1][j]);
            }
        }
    }
}

int max(int a, int b)
{
    return (a > b) ? a : b;
}

Answer 1

Valgrind 报告：

==8563== Invalid read of size 4
==8563==    at 0x108977: knapsack (17640299.c:53)
==8563==    by 0x108831: main (17640299.c:23)
==8563==  Address 0x4 is not stack'd, malloc'd or (recently) free'd

这是在循环中：

    for ( int j = 1; j < max_weight + 1; j += 1 )
    {
        int w = *(items->weight + i); //weight of current item
        int v = *(items->value + i); //value of current item

（我不确定为什么没有将它们分别写成更具可读性的 items->weight[i] 和 items->value[i]）。

我重写了方法，读起来更清楚，再也不会触发这个故障了：

void knapsack(const Items_knapsack *items,
              int solution[items->total_items+1][items->max_weight + 1])
{
    const int total_items = items->total_items;
    const int max_weight = items->max_weight;

    for (int i = 0;  i <= total_items;  ++i)
        for (int j = 0;  j <= max_weight;  ++j)
            solution[i][j] = 0;

    for (int i = 1;  i <= total_items;  ++i) {
        const int w = items->weight[i]; //weight of current item
        const int v = items->value[i]; //value of current item

        for (int j = 1;  j <= max_weight;  ++j) {
            if (w > j) {
                solution[i][j] = solution[i-1][j];
            } else {
                solution[i][j] = max(v + solution[i-1][j-w],
                                     solution[i-1][j]);
            }
        }
    }
}

0-1背包使用动态规划实现

0-1 knapsack implementation using dynamic programming

c

algorithm

knapsack-problem

dynamic-programming

segmentation-fault