|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
06.03.2011, 11:59 | #1 |
Новичок
Джуниор
Регистрация: 06.03.2011
Сообщений: 1
|
Программа на рекурсию
Задача о рюкзаке. В рюкзаке объёмом V содержится запас из N предметов. Для каждого предмета задан объем и стоимость. В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы общая стоимость упакованных предметов была наибольшей, а их общий объём не превосходил V. Форма предметов в задаче не рассматривается.
Попробовал сам написать программу. Но после выполнения команды return, функция продолжает дальше работать!? Вот код: #include <iostream> #include <fstream> extern struct thing { float price,size; char name[15]; }; int f(int Pos, float MaxV, thing *arr, int n,FILE *out, float CurV); int main() { setlocale(LC_ALL,"Rus"); float MaxV,CurV=0; std::cout<<"\tДанная программа решает следующую задачу:\n" "В рюкзаке объёмом V содержится запас из N предметов. Для каждого\n" "предмета задан объем и стоимость. В рюкзак можно положить целое число\n" "различных предметов. Нужно упаковать рюкзак так, чтобы общая стоимость\n" "упакованных предметов была наибольшей, а их общий объём не превосходил V.\n" "Форма предметов в задаче не рассматривается."<<std::endl; std::cout<<"\nВведите имя исходного файла: "; char InName[15],OutName[15]; std::cin>>InName; FILE *in,*out; if(!(in=fopen(InName,"r"))) { std::cout<<"\nФайл не открыт."<<std::endl; system("PAUSE"); return 0; } std::cout<<"Введите объём рюкзака: "; std::cin>>MaxV; thing *arr,tmp; int fl=0,n=0,i=0,MCost=0; std::cout<<"Введите кол-во предметов: "; std::cin>>n; arr=new thing[n]; std::cout<<"\nСодержание файла "<<InName<<":"<<std::endl; std::cout<<"-----------------------------------"<<std::endl; std::cout<<"Название\tОбъём\tЦена"< <std::endl; std::cout<<"-----------------------------------"<<std::endl; for(i=0;i<n;++i) { fscanf(in,"%s%f%f",arr[i].name,&arr[i].size,&arr[i].price); std::cout<<arr[i].name<<"\t\t"<<arr[i].size<<"\t"<<arr[i].price<<std::endl; } fclose(in); do { fl=0; for(i=0;i<n-1;++i) if(arr[i].price<arr[i+1].price) {tmp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=tmp; fl=1;} } while(fl==1); puts("test:"); for(i=0;i<n;++i) std::cout<<arr[i].name<<"\t\t"<<arr[i].size<<"\t"<<arr[i].price<<std::endl; std::cout<<"\nВведите имя выходного файла: "; std::cin>>OutName; out=fopen(OutName,"w+"); f(0,MaxV,arr,n,out,CurV); std::cout<<"\nВещи в рюкзаке:"<<std::endl; std::cout<<"-----------------------------------"<<std::endl; std::cout<<"Название\tОбъём\tЦена"< <std::endl; std::cout<<"-----------------------------------"<<std::endl; rewind(out); fscanf(in,"%s%f%f",tmp.name,&tmp.si ze,&tmp.price); while(!feof(out)) { std::cout<<tmp.name<<"\t\t"<<tmp.si ze<<"\t"<<tmp.price<<std::endl; fscanf(in,"%s%f%f",tmp.name,&tmp.si ze,&tmp.price); } system("PAUSE"); fclose(out); delete []arr; return 0; } int f(int Pos, float MaxV, thing *arr, int n, FILE *out, float CurV) { float _CurV=CurV; if(arr[Pos].size>MaxV) f(Pos+1,MaxV,arr,n,out,CurV); if(Pos==n-1) { CurV+=arr[Pos].size; if(CurV>MaxV) return 0; fprintf(out,"%s\t%.1f\t%.1f\n",arr[Pos].name,arr[Pos].size,arr[Pos].price); return 0; } else { CurV+=arr[Pos].size; if(CurV>MaxV) f(Pos+1,MaxV,arr,n,out,_CurV); fprintf(out,"%s\t%.1f\t%.1f\n",arr[Pos].name,arr[Pos].size,arr[Pos].price); f(Pos+1,MaxV,arr,n,out,CurV); } } Содержание входного файла: aaa 0,5 20 bbb 0,3 10 ccc 1,2 40 ddd 0,4 40 eee 5 100 fff 0,1 30 ggg 0,5 74 hhh 2 76 Программа работает неправильно... Если объём рюкзака равен объёму предмета, то программа записывает в файл предмет, когда можно из более мелких предметов получить более дорогую совокупность!? |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача на рекурсию | Rusl92 | Помощь студентам | 1 | 13.01.2011 22:36 |
Задача на рекурсию(( | kinza | Помощь студентам | 6 | 08.06.2009 09:51 |
Задача на рекурсию. | KoHgpaT | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 22.12.2006 20:49 |