Добре, опитвам се да реша проблема с раницата.
При малки входни случаи програмата работи без проблем и осигурява оптималното решение, но когато входният размер е голям или по-скоро числата във входния файл станат големи, програмата ми дава грешка при сегментиране. Не разбирам съвсем защо се случва това, след като максималната стойност на INT надвишава и някое от тези числа.
Ето моя код.
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int W,n,i,j,k ;
scanf("%d %d",&W,&n); // capacity of knapsack and number of total items
int value[n+1],weight[n+1];
int** A;
A = (int **)malloc((n+1)*sizeof(int*));
for(i=0;i<W+1;i++)
A[i]=(int *)malloc(sizeof(int)*(W+1));
for(i=1;i<n+1;i++)
{
scanf("%d %d",&value[i],&weight[i]); //taking value and weight of each item
}
for(i=0;i<W+1;i++)
A[0][i]=0;
for(i=0;i<n+1;i++)
A[i][0]=0;
for(i=1;i<n+1;i++)
{
for(j=1;j<W+1;j++)
{
if(j-weight[i]<0)
{
A[1][j]=A[0][j];
}
else
{
if(A[0][j]>A[0][j-weight[i]]+value[i])
A[1][j]=A[0][j];
else
A[1][j]=A[0][j-weight[i]]+value[i];
}
}
for(k=0;k<W+1;k++)
A[0][k]=A[1][k];
}
int max=0;
i=1;
for(i=0;i<2;i++)
for(j=0;j<W+1;j++)
{
if(A[i][j]>max)
max=A[i][j];
}
printf("%d\n",max);
return(0);
}
Работи перфектно за този вход http://spark-public.s3.amazonaws.com/algo2/datasets/knapsack1.txt
Но когато размерът на входа е този, даден във връзката, той предоставя грешка в сегмента http://spark-public.s3.amazonaws.com/algo2/datasets/knapsack2.txt Благодаря за помощта!
int value[n+1],weight[n+1];
Това дори не трябва да се компилира. - person sgarizvi   schedule 04.01.2013C99
, нито е споменат във въпроса. - person sgarizvi   schedule 04.01.2013