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

работа в С++ - C++

Восстановить пароль Регистрация
 
Veina
0 / 0 / 0
Регистрация: 25.11.2009
Сообщений: 12
09.12.2009, 12:00     работа в С++ #1
В текстовом файле записаны названия некоторых предметов, а так же их веса и ценности. При заданном ограничении на суммарный вес предметов, сформировать набор, имеющий наибольшую совокупную ценность.
Например:
задается:
мишка_0,3кг_200р.
молоко_0,1кг_20р.
диван_12кг_5000р.
стул_2кг_2000р.
кресло_9кг_4000р.
парта_7кг_1500р.
монитор_20кг_25000р.
холодильник_20кг_25000кг.
телевизор_17кг_13000р.

задается вес не более 50 кг, т. е. сформировать набор не более, чем на 50 кг. из предметов наибольшей ценности.
результат должен быть таким:
холодильник_20кг_25000р.
монитор_4кг_15000р.
телевизор_17кг_13000р.
итог: 41кг_53000р.

помогите, пожалуйста. очень нужна эта задача.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
09.12.2009, 12:09     работа в С++ #2

Не по теме:

это в помощь начинающему налётчику?



посчитайте весовой коэффициент всех предметов как отношения веса к стоимости и по максимальному результату заполняйте пока вес не достигнет около 50ти киллограммовой величины.
Veina
0 / 0 / 0
Регистрация: 25.11.2009
Сообщений: 12
09.12.2009, 16:00  [ТС]     работа в С++ #3
можно ввиде кода? я сама не программист, но мне нужна эта задача. очень-очень...
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
09.12.2009, 19:49     работа в С++ #4
ты хоть фаил запомни и организуй чтение из него. времени нет всё делать.
да я ктому же тоже не программист
Veina
0 / 0 / 0
Регистрация: 25.11.2009
Сообщений: 12
10.12.2009, 15:17  [ТС]     работа в С++ #5
есть кое какие наброски. посмотри
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
#include <vector>
#include <limits>
 
int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
    size_t n = wts.size();
    std::vector<std::vector<int> > dp(W + 1);
    for (int i = 0; i <= W; i++)
    {
        dp[i].resize(n + 1);
        dp[i][0] = 0;
    }
    for (size_t i = 0; i <= n; i++)
    {
        dp[0][i] = 0;
    }
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (wts[j-1] <= w)
            {
                dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
            } else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}
Veina
0 / 0 / 0
Регистрация: 25.11.2009
Сообщений: 12
11.12.2009, 21:03  [ТС]     работа в С++ #6
ну помогите же кто-нибудь. пожалуйста. очень прошу(((
Yandex
Объявления
11.12.2009, 21:03     работа в С++
Ответ Создать тему
Опции темы

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