Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
wertrix
0 / 0 / 1
Регистрация: 01.10.2010
Сообщений: 49
1

Программа на рекурсию

05.03.2011, 14:44. Просмотров 1005. Ответов 3
Метки нет (Все метки)

Задача о рюкзаке. В рюкзаке объёмом V содержится запас из N предметов. Для каждого предмета задан объем и стоимость. В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы общая стоимость упакованных предметов была наибольшей, а их общий объём не превосходил V. Форма предметов в задаче не рассматривается.
Как написать функцию упаковывания!?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2011, 14:44
Ответы с готовыми решениями:

Программа на рекурсию - Перестановка !
Доброго времени суток, уважаемые знатоки. Возникла проблема с решением данной программы. Надеюсь...

Почему программа уходит в рекурсию при передачи в нее буквы
Здравствуйте, простите за два идиотских вопроса, но почему С++ ведет себя именно так? Почему...

Код Фано, программа не заканчивает рекурсию
Здравствуйте! Мне необходимо закодировать текст на английском языке кодом Фано. Все делаю по...

Не понятно как работает программа на рекурсию.
Эта программа вычисляет квадраты всех целых чисел от нуля до введённого натурального n, не...

Нужна программа, использующая рекурсию, с пояснением ее работы
Здравствуйте. Помогите пожалуйста! Мне нужно две простеньких программы по рекурсии с пояснениями...

3
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
05.03.2011, 15:03 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
int n, maxV, maxCost = 0;
vector<int> v, cost, ans, curAns;
 
void f(int pos, int curV, int curCost)
{
    if(curV > maxV)
        return;
    if(pos == n)
    {
        if(curCost > maxCost)
        {
            maxCost = curCost;
            ans = curAns;
        }
    }
    else
    {
        f(pos+1,curV,curCost);
 
        curAns.push_back(pos);
        f(pos+1,curV+v[pos],curCost+cost[pos]);
        curAns.pop_back();
    }
}
 
int main()
{   
    cin >> n >> maxV;
    v.resize(n);
    cost.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i] >> cost[i];
    f(0,0,0);
    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
}
1
wertrix
0 / 0 / 1
Регистрация: 01.10.2010
Сообщений: 49
06.03.2011, 13:26  [ТС] 3
Попробовал сам написать программу. Без глобальных переменных (исключая структуру вещи), и без векторов. Но после выполнения команды return, функция продолжает дальше работать!? Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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.size,&tmp.price);
    while(!feof(out))
    {
        std::cout<<tmp.name<<"\t\t"<<tmp.size<<"\t"<<tmp.price<<std::endl;
        fscanf(in,"%s%f%f",tmp.name,&tmp.size,&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

Помогите разобраться, пожалуйста!

Добавлено через 2 часа 40 минут
Если объём рюкзака равен объёму предмета, то программа записывает в файл предмет, когда можно из более мелких предметов получить более дорогую совокупность!?
0
wertrix
0 / 0 / 1
Регистрация: 01.10.2010
Сообщений: 49
09.03.2011, 17:25  [ТС] 4
Кстати, разобрался, вроде пашет Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <fstream>
 
extern struct thing
{
    int price,size;
    char name[15];
    float otn;
};
 
void f(FILE *out, thing *arr, int i, int MaxV, int CurV, int n);
 
int main()
{
    setlocale(LC_ALL,"Rus");
    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;
    }
    int MaxV,fl,n,i=0;
    std::cout<<"Введите объём рюкзака: ";
    std::cin>>MaxV;
    thing *arr,tmp;
    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%d%d",arr[i].name,&arr[i].size,&arr[i].price);
        arr[i].otn=(float)arr[i].price/(float)arr[i].size;
        std::cout<<arr[i].name<<"\t\t"<<arr[i].size<<"\t"<<arr[i].price<<std::endl;
    }
    std::cout<<"-----------------------------------"<<std::endl;
    fclose(in);
    do
    {
        fl=0;
        for(i=0;i<n-1;++i)
            if(arr[i].otn<arr[i+1].otn)
            {
                tmp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=tmp;
                fl=1;
            }
    }
    while(fl==1);
    std::cout<<"\nВведите имя файла-рюкзака: ";
    std::cin>>OutName;
    out=fopen(OutName,"w+");
    f(out,arr,0,MaxV,0,n);
    std::cout<<"\nВещи в рюкзаке:"<<std::endl;
    std::cout<<"-----------------------------------"<<std::endl;
    std::cout<<"Название\tОбъём\tЦена"<<std::endl;
    std::cout<<"-----------------------------------"<<std::endl;
    rewind(out);
    int SumV=0,SumCost=0;
    fscanf(out,"%s%d%d",tmp.name,&tmp.size,&tmp.price);
    while(!feof(out))
    {
        SumV+=tmp.size;
        SumCost+=tmp.price;
        std::cout<<tmp.name<<"\t\t"<<tmp.size<<"\t"<<tmp.price<<std::endl;
        fscanf(out,"%s%d%d",tmp.name,&tmp.size,&tmp.price);
    }
    std::cout<<"-----------------------------------"<<std::endl;
    std::cout<<"Объём вещей в рюкзаке: "<<SumV<<std::endl;
    std::cout<<"Цена вещей в рюкзаке: "<<SumCost<<std::endl;
    system("PAUSE");
    fclose(out);
    delete []arr;
    return 0;
}
 
void f(FILE *out, thing *arr, int i, int MaxV, int CurV, int n)
{
    if(CurV>MaxV)
        return;
    if(i==n)
    {
        return;
    }
    else
    {
        if((CurV+arr[i].size)>MaxV)
        {
            f(out,arr,i+1,MaxV,CurV,n);
        }
        else
        {
            fprintf(out,"%s\t%d\t%d\n",arr[i].name,arr[i].size,arr[i].price);
            f(out,arr,i+1,MaxV,CurV+arr[i].size,n);
        }
    }
}
0
09.03.2011, 17:25
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2011, 17:25

Переделать рекурсию по аргументу в рекурсию по значению
эта рекурсия по аргументу, заменяющая Y на число, равное глубине вложения Y в список List,...

3адача на рекурсию
Написать функцию, которая указанный элемент заменяет на новый. допустим есть список ( 1 2 3 4 5...

Задача на рекурсию
const n=...; type vector = array of real; Описать рекурсивную функцию max (x) для определения...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.