Implémentation du knapsack 0-1 à l'aide de la programmation dynamique

Question

Fonctionne correctement pour les valeurs de poids, de valeur, de poids maxi et de total_items mais donne des erreurs de segmentation lorsque je change le poids, la valeur et d'autres variables.

J'ai vérifié que lorsque je change les variables alors dans la fonction de sac à dos items->value et items->weight devient NULL.

et items->max_weight et items->total_items devient 0.

Je n'arrive pas à comprendre ce qui ne va pas dans mon code, merci de nous aider, merci d'avance.

code

#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 rapports:

==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 

Ceci est dans la boucle:

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 

(Je ne sais pas pourquoi ceux qui ne sont pas écrits comme plus lisibles items->weight[i] et items->value[i] vely).

Je re-écrit la méthode pour être plus clair à lire, et ne pouvait plus déclencher cet échec:

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