동적 프로그래밍을 사용한 0-1 배낭 구현

Question

주어진 weight, value, max_weight 및 total_item 값에 대해서는 잘 작동하지만 가중치, 값 및 기타 변수를 변경하면 세그먼트 화 오류가 발생합니다.

변수를 변경할 때 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] 영역 vely).

내가 다시 쓴 방법 읽을 명확하게하기 위해, 더 이상이 실패 발동 수 :

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