Форум программистов, компьютерный форум CyberForum.ru

Обратная задача о ранце (ДП) - C++

Восстановить пароль Регистрация
 
El studentos
0 / 0 / 0
Регистрация: 15.10.2012
Сообщений: 5
14.05.2013, 06:30     Обратная задача о ранце (ДП) #1
Здравствуйте, необходимо решить типичную задачу о ранце, в двух видах.

1. Выбрать предметы с общей максимальной ценностью при весе не превышающем N.
2. Набрать предметов на стоимость близкую(не больше) или равную M, при минимальном весе этих предметов.

Решил первую часть сам:


Данные вес/ценность взял из википедии.
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
#include <stdio.h>
#include <stdlib.h>
 
#define W 14
#define N 4
 
 
 
int lmax(int a, int b){
    return a > b ? a : b;
}
 
void findAns(int k, int s, int A[N+1][W+1], int w[N], int p[N]){
    if(A[k][s] == 0)
        return;
 
    if(A[k-1][s] == A[k][s])
        findAns(k-1, s, A, w, p);
    else{
        findAns(k-1, s - w[k], A, w, p);
        printf("predmet_%d: ves=%d tsennost=%d\n", k, w[k], p[k]);
    }
}
 
 
int main(){
    int i, k, s, kd;
    int A[N+1][W+1];
    int w[N], p[N];
 
    w[1] = 5;   p[1] = 3;
    w[2] = 10;  p[2] = 5;
    w[3] = 6;   p[3] = 4;
    w[4] = 5;   p[4] = 2;
 
 
    for(i = 0; i <= W; i++)
        A[0][i] = 0;
 
    for(i = 0; i <= N; i++)
        A[i][0] = 0;
 
    for(k = 1; k <= N; k++){
        printf("predmet_%d: ves=%d tsennost=%d\n ", k, w[k], p[k]);
        for(s = 1; s <= W; s++){
            printf("%d >= %d: \n", s, w[k]);
            if(s >= w[k]){
                A[k][s] = lmax(A[k-1][s], A[k-1][s-w[k]]+p[k]);
                printf("\tA[%d][%d] = max(%d, %d) = %d\n", k, s, A[k-1][s], A[k-1][s-w[k]]+p[k], A[k][s]);
            }else{
                A[k][s] = A[k-1][s];
                printf("\tA[%d][%d]/%d/ = A[%d][%d]/%d/\n", k, s, A[k][s], k-1, s, A[k-1][s]);
            }
 
            printf("A[%d][%d] = %d\n\n", k, s, A[k][s]);
        }
        printf("\n");
    }
 
    printf("\n\n----------------------------------------------\n");
    for(k = 1; k <= N; k++){
        for(s = 1; s <= W; s++)
            printf("%d ", A[k][s]);
        printf("\n");
    }
    printf("----------------------------------------------\n");
 
    findAns(k - 1, s - 1, A, w, p);
 
    return 0;
}

А со второй тема не понятна, в интернете нашел кучу различных математических выражений по этому поводу, но не додумал как это всё-таки реализовать.

Помогите кодом, пожалуйста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2013, 06:30     Обратная задача о ранце (ДП)
Посмотрите здесь:

о ранце C++
C++ Обратная матрица
Задача о ранце. Исправить ошибки в приведенном коде C++
Обратная мартрица C++
C++ Задача о ранце
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
El studentos
0 / 0 / 0
Регистрация: 15.10.2012
Сообщений: 5
15.05.2013, 11:09  [ТС]     Обратная задача о ранце (ДП) #2
Неужели никто не знает?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
15.05.2013, 14:33     Обратная задача о ранце (ДП) #3
El studentos, постановка задачи во втором пункте некорректна, мне непонятно следующее : Нужно набрать max стоимость <= M, но их всех таких наборов, которые дают этот вес, нужно выбрать такой, что в нём больше монет ?

El studentos, кстати, первую задачу я раньше решал вот так :
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
#include <iostream>
#include <vector>
#include <limits>
 
using namespace std;
 
int main(){         
    vector <int> ranec(1001, -INT_MAX);
    ranec[0] = 0;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        int w, c;
        cin >> w >> c;
        for (int j = q - w; j >= 0; j--){
            if (ranec[j] != -INT_MAX){
                ranec[j + w] = max(ranec[j + w], ranec[j] + c);
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= q; j++){
            ans = max(ranec[j], ans);
    }
    cout << ans;
    return 0;
}
El studentos
0 / 0 / 0
Регистрация: 15.10.2012
Сообщений: 5
16.05.2013, 07:51  [ТС]     Обратная задача о ранце (ДП) #4
Цитата Сообщение от Ternsip Посмотреть сообщение
El studentos, постановка задачи во втором пункте некорректна, мне непонятно следующее : Нужно набрать max стоимость <= M, но их всех таких наборов, которые дают этот вес, нужно выбрать такой, что в нём больше монет ?

El studentos, кстати, первую задачу я раньше решал вот так :
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
#include <iostream>
#include <vector>
#include <limits>
 
using namespace std;
 
int main(){         
    vector <int> ranec(1001, -INT_MAX);
    ranec[0] = 0;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        int w, c;
        cin >> w >> c;
        for (int j = q - w; j >= 0; j--){
            if (ranec[j] != -INT_MAX){
                ranec[j + w] = max(ranec[j + w], ranec[j] + c);
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= q; j++){
            ans = max(ranec[j], ans);
    }
    cout << ans;
    return 0;
}
Нужно набрать предметов к примеру на 10кг, при их наименьшем весе.

К примеру есть предметы
вес | ценность
3 | 5
2 | 4
5 | 5
4 | 1

Нужно набрать на 10 монет, при минимальном весе набора.
Сейчас у нас есть варианты для набора: 1-3, 1-2-4, 2-3-4, соответсвенно минимальный вес из данных наборов будет равен 8, т.е. набор 1-3.

Задача такова)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
16.05.2013, 14:46     Обратная задача о ранце (ДП) #5
El studentos,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <limits>
 
using namespace std;
 
int main(){    
    vector <int> ranec(1001, INT_MAX);
    ranec[0] = 0;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        int w, c;
        cin >> c >> w;
        for (int j = q - w; j >= 0; j--){
            if (ranec[j] != INT_MAX){
                ranec[j + w] = min(ranec[j + w], ranec[j] + c);
            }
        }
    }
    cout << ranec[q];
    return 0;
}
Пример ввода, соотв вашему примеру :
4 10
3 5
2 4
5 5
4 1

Добавлено через 49 секунд
El studentos, если набрать невозможно выводит 2147483647
Yandex
Объявления
16.05.2013, 14:46     Обратная задача о ранце (ДП)
Ответ Создать тему
Опции темы

Текущее время: 12:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru