在客觀上創建一個適當的揹包邏輯C

Question

我有這個揹包邏輯代碼工作在我的應用程序，但如果數組太大，我會經常在C數組上得到exc_bad_access code=2，我找不到原因並希望你們可以啓迪我的代碼出了什麼問題。

//main chunk of code for Knapsack logic 
-(NSMutableArray*)knapsackWithWeightArray:(NSMutableArray*)weightArray andLimits:(NSInteger)WLimits 
{ 
    NSMutableArray *keepSongs = [[NSMutableArray alloc]initWithCapacity:WLimits];//array to keep songs 
    NSInteger N = [weightArray count]; // number of items 
    NSInteger option[N+1][WLimits+1]; // opt[n][w] = max profit of packing items 1..n with weight limit w 
    bool sol[N+1][WLimits+1]; //does opt solution to pack items 1..n with weight limit w include item n? 
    NSInteger totalDuration = 0; 
    for (NSInteger n = 1; n<= N; n++) // no of items 
    { 
     for (NSInteger w = 1; w <= WLimits; w++) // loop for weights 
     { 
      WeightObject *wObj = weightArray[n-1]; 
      NSInteger opt1 = option[n-1][w]; // crash here 
      NSInteger opt2 = INT32_MIN; 
      NSInteger knWeight = wObj.weight; 

      if (knWeight <= w) 
      { 
       opt2 = wObj.Value + option[n-1][w - knWeight]; // crash here 
      } 
      // select better of two options 
      option[n][w] = MAX(opt1, opt2); // crash here 
      sol[n][w] = opt2 > opt1; // ensure opt & sol same size. // crash here 
     } 
    } 

    // determine which items to take 
    for (NSInteger n = N, w = WLimits; n > 0; n--) 
    { 
     if (sol[n][w]) 
     { 
      w = w - [weightArray[n-1]weight]; 
      WeightObject *obj = weightArray[n-1]; 
      totalDuration = totalDuration + obj.weight; 
      [keepSongs addObject:obj.songObj]; 
     } 
    } 
    NSLog(@"knapsackWithWeightArray totalDuration %d",totalDuration); 
    return keepSongs; 
} 

Answer 1

我固定的變化問題C數組來的OBJ數組c

//main chunk of code for Knapsack logic 
-(NSMutableArray*)knapsackWithWeightArray:(NSMutableArray*)weightArray andLimits:(NSInteger)WLimits 
{ 
    NSMutableArray *keepSongs = [[NSMutableArray alloc]initWithCapacity:WLimits]; 
    NSInteger N = [weightArray count]-1; // number of items 
    NSMutableArray *optionA = [NSMutableArray arrayWithCapacity:(N+1)]; //first [] 
    NSMutableArray *solA = [NSMutableArray arrayWithCapacity:(N+1)]; //first [] 

    for (NSInteger i=0; i<(N+1); i++) 
    { 
     optionA[i] = [NSMutableArray arrayWithCapacity:WLimits + 1];//init second [] 
     solA[i] = [NSMutableArray arrayWithCapacity:WLimits + 1]; //init second [] 

     for (NSInteger j=0; j<(WLimits+1); j++) 
     { 
      optionA[i][j] = @0; //fill with zero 
      solA[i][j] = @0; //fill with zero 
     } 
    } 

    NSInteger totalDuration = 0; 

    for (NSInteger n = 1; n<= N; n++) // no of items 
    { 
     for (NSInteger w = 1; w <= WLimits; w++) // loop for weights etc 900 
     { 
      WeightObject *wObj = weightArray[n-1]; 
      //don't take item n 
      //NSInteger opt1 = option[n-1][w]; 
      NSInteger opt1 = [optionA[n-1][w] integerValue]; 
      NSInteger opt2 = INT32_MIN; 

      // take item n 
      NSInteger knWeight = wObj.weight;//[weightArray[n-1]weight]; 

      if (knWeight <= w) 
      { 
       //opt2 = [weightArray[n-1]Value] + option[n-1][w - knWeight]; 
       opt2 = wObj.Value + [optionA[n-1][w - knWeight] integerValue]; 
      } 
      // select better of two options 
      optionA[n][w] = @(MAX(opt1, opt2)); 
      //sol[n][w] = opt2 > opt1; // ensure opt & sol same size. 
      solA[n][w] = @(opt2 > opt1); 
     } 
    } 

    // determine which items to take 
    for (NSInteger n = N, w = WLimits; n > 0; n--) 
    { 
     if ([solA[n][w]boolValue]) 
     { 
      w = w - [weightArray[n-1]weight]; 
      WeightObject *obj = weightArray[n-1]; 
      totalDuration = totalDuration + obj.weight; 
      [keepSongs addObject:obj.songObj]; 
     } 
    } 
    NSLog(@"knapsackWithWeightArray totalDuration %d",totalDuration); 
    return keepSongs; 
}