C - 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]);
            }
        }
    }
}