[raffaello]

Vaja oli leida lahendus täisarvulisele seljakoti pakkimise ülesandele kasutades sügavuti otsivat (tagasivõtmisega - backtracking) algoritmi.
Põhiülesandeks oli realiseerida tagasivõtmisega rekursiivne algoritm koos kärpimisega.

Siin see kood siis on kuid miskipärast ei väljasta ta vastust. Ehk siis väljastab nii kaua kui input.txt ei eksisteeri. Siis ütleb kenasti et "sisendfaili ei leitud". Kui aga input.txt on olemas, väljastab ainult tühja rea, isegi mitte mingeid veateateid. Ma ei suuda leida milles võiks probleem olla. kas keegi oskab aidata?

Kood ise:
#include <stdio.h>
#include <stdlib.h>

int maxprofit=0; //maksimaalne leitud asjade kogukasum
int maxweight=0; //maksimaalne leitud asjade kogukaal
int total_weight; //lubatud maksimaalne kaal


ty****f struct item thing;
struct item{
int price;
int weight;
double relationship;
};
void pack(int i, int profit, int weight);
int promising(int i, int weight, int profit);
int compare(const void * a, const void * b);




thing items[5000];

int include[5000]; // seljakotis olevad asjad
int maxinclude[5000]; // maksimaalsed asjad
int find;
int i_max; //maksimaalse elemendi väärtus

int main(void)
{
int j; // for tsükli jaoks
FILE *pFile;// = stdin;
pFile = fopen("input.txt", "r");
if( !pFile ) {
printf("Sisendfaili ei ole");

return 1;
}

//sisendi lugemine
fscanf(pFile,"%d",&total_weight);//loeb täisarvu failist

for(i_max = 0 ;!feof(pFile);i_max++)
{
fscanf(pFile,"%d %d\n",&items[i_max].price,&items[i_max].weight);
items[i_max].relationship = (double)items[i_max].price/(double)items[i_max].weight;
//kas fail lõppenud
}
qsort(items,i_max+1,sizeof(thing),compare);
for(j=0;j<101;j++){

}
//arvutamine
//include[0]=1;
//pack(0, 0, 0);//esimene element, kaal, väärtus
//include[0]=0;
pack(0,0,0);

//vastuse väljatrükk
printf("Maximaalsed \n%d %d\n\n Kotti vottis\n" , maxprofit, maxweight);

for(j=0; j<=find; j++)
{
if(maxinclude[j])
printf("%d %d\n",items[j].price, items[j].weight);

}
//getchar();
return 0;
}

void pack(int i, int profit, int weight){
int j;

if( weight > total_weight)
return;

if( profit > maxprofit)
{
maxprofit = profit;
maxweight = weight;
find = i;
for( j=0; j<=i; j++ )
{
maxinclude[j]=include[j];
}
}


//kärpimine
if( promising(i, weight, profit))
{
include[i]=1;
pack(i+1, profit + items[i+1].price, weight + items[i+1].weight);
include[i]=0;
pack(i+1, profit, weight);
}
}


int promising(int i, int weight, int profit){
int totalWeight;
float totalProfit;
int j = i+1;

if( weight > total_weight )
return 0;


totalProfit = profit;
totalWeight = weight;

while( j <= i_max && totalWeight + items[j].weight < maxweight )
{
totalWeight=totalWeight+items[j].weight;
totalProfit=totalProfit+items[j].price;
j++;
}


if( totalProfit >= maxprofit )
return 1;

return 0;
}

int compare(const void *a, const void* b)
{
struct item *item1 = (struct item*)a;
struct item *item2 = (struct item*)b;

if( item1->relationship > item2->relationship )
return -1;
else if( item1->relationship < item2->relationship )
return 1;
return 0;
}



Ja sisendfailiks siis oleks lihtne txt laiendiga fail kujul:
105
11 21
17 27
19 29
17 27
12 22
19 29
22 32
16 26
23 33
18 28
15 25
22 32
12 22
16 26
17 27
22 32
14 24
17 27

[nene]

Äkki sa saaksid oma koodi panna [ code ] ja [ / code ] märgendite vahele, et oleks natukegi loetavam.

Või veelgi parem - [ syntax="c" ] ja [ / syntax ] vahele - siis on ka süntaks kenasti esile tõstetud.

[ref]

kooliülesanne ttüs ? kuidagi tuttav teema

[andreie]

Ma loeksin ka heameelega koodi, aga treppimata kood on hirmus nüri ja pealegi ilmselge kooliülesanne. Senikaua saan aidata ainult silumisega.

Silumine - see on imelihtne!

1. Teed andmefaili "input.txt" lühemaks, näiteks kaherealiseks.
2. Avad programmi IDE-s.
3. Käid samm-sammult programmi läbi (single-stepping, näiteks MSVC menüüs "Debug -> Step over" või "Debug -> Step into"), otsides loogikavigu.
4. Kui leidsid, siis parandada.
5. Vajadusel korrata.

[raffaello]

[nene]

Õigupoolest mina ei saa küll aru, mida su kood üldse teha üritab... Kui sa ütled et ta tegeleb täisarvulise seljakoti pakkimise ülesandega, siis see ei ütle mulle küll mitte midagi. Võimalik, et tegemist on populaarse kooliülesandega, aga mulle juhtumisi täiesti tundmatu.

Lisaks on su koodis väga müstilisi asju...

Milleks näiteks see:

[pinfo]

Selle ülesande lahendamise saab jagada etappideks.

1) kirjuta rekurssiivne kõigi seljakottide väljaarvutamine (saad kokku 2 astmes N kaalu-hinna komplekti). Testi see ära.
2) Lisa rekursioonile piirang mis ei lase etteantud maksimumkaalu ületada.
3) Lisa kärpimine.