수다닷컴

질문 제목 : c언어 부분 배낭 문제 관련 질문
부분 배낭문제 소스 어디를 수정 해야 하나요?
질문 내용 :
제가 부분 배낭 문제를 짜게 되었는데요. 지인 들의 도움으로 오류를잡고 짠 것 까지는 좋은데 제가 원하는게 나오지 않습니다. 구해서 그 가치의 최대값 까지는 나오는데 그 값들에 해당하는계획 값들을 어떻게 표시해야 될지 모르겠습니다. 아래는 부분 배낭 문제를 응용해서 하루 12시간을 잡고 계획 을 짤때 어떤 걸로 정해야 최대의 가치를 나타낼지를 정하는 소스 입니다, 가치는 출력이 되지만 그 가치들이 해당되는 과목들을 어떻게 출력해야 될지 모르겠습니다. 예를 들어 오늘 계획은 숙제, 공부, 게임, 운동 이고 각각o시간 o시간 o시간 o시간을 수행해야 합니다.아시는분 알려주세요.
#include stdio.h
#include stdlib.h
typedef struct item
{
int hour;
int value;
}item;
int compare(const void *x, const void *y)
{
item *i1 = (item *)x, *i2 = (item *)y;
double ratio1 = (*i1).value*1.0 / (*i1).hour;
double ratio2 = (*i2).value*1.0 / (*i2).hour;
if(ratio1 ratio2)
return 1;
else if(ratio1 ratio2)
return -1;
else
return 0;
}
int main()
{
int items;
printf(오늘의 목표 숙제 잠 공부 간식 게임 운동 밥.);
printf(오늘 할 계획의 수를 입력하세요. : );
scanf(%d,&items);
item *i=(item*)malloc(sizeof(item)*items);

int iter;
for(iter=0;iteritems;iter++)
{
printf(순서대로 시간과 그것의 가치를 적으시오. : );
scanf(%d%d,&i[iter].hour,&i[iter].value);
}
qsort(i,items,sizeof(item),compare);

int maxhour;
printf(오늘 할 최대의 시간은? : );
scanf(%d,&maxhour);
double value = 0.0;
int presenthour = 0;
for(iter=0;iteritems;iter++)
{
if(presenthour + i[iter].hour maxhour)
{
presenthour = presenthour + i[iter].hour;
value += i[iter].value;
}
else
{
int remaining = maxhour - presenthour;
value += i[iter].value*remaining *1.0/i[iter].hour;
break;
}
}
printf(계산을 해서 12시간 동안 달성할수 있는 최대 값은 %.6lf 이다.\n,value);
}

신청하기