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

У покупателя есть n монет достоинством H(1)...H(n) - C++

Восстановить пароль Регистрация
 
boom299
2 / 2 / 0
Регистрация: 08.04.2011
Сообщений: 23
08.05.2011, 22:41     У покупателя есть n монет достоинством H(1)...H(n) #1
У покупателя есть n монет достоинством H(1)...H(n). У продавца есть m монет достоинством B(1)...B(l). Может ли купить покупатель вещь стоимостью S так, чтобы у продавца нашлась точная сдача (если она необходима)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.05.2011, 22:41     У покупателя есть n монет достоинством H(1)...H(n)
Посмотрите здесь:

Среди 13 монет есть одна отличающаяся по весу, за 3 взвешивания на чашечных весах найти ее C++
Определить время Ci пребывания i-го покупателя в очереди C++
Определить время пребывания i-го покупателя в очереди C++
C++ составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством в1,2,3,5 копеек)
автомат по размену монет C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
08.05.2011, 22:47     У покупателя есть n монет достоинством H(1)...H(n) #2
Цитата Сообщение от boom299 Посмотреть сообщение
У покупателя есть n монет достоинством H(1)...H(n). У продавца есть m монет достоинством B(1)...B(l). Может ли купить покупатель вещь стоимостью S так, чтобы у продавца нашлась точная сдача (если она необходима)
все монеты покупателя берутся с +, продавца с -, S тоже с минусом, нужно составить нулевую сумму, можно прибавить ко всему константу, чтобы все стало неотрицательным и через динамическое программирование, в массиве идти до суммы S+константа
povtiasd051
2 / 2 / 0
Регистрация: 06.12.2010
Сообщений: 135
12.07.2011, 18:05     У покупателя есть n монет достоинством H(1)...H(n) #3
Цитата Сообщение от eXXXXXXXXXXX Посмотреть сообщение
все монеты покупателя берутся с +, продавца с -, S тоже с минусом, нужно составить нулевую сумму, можно прибавить ко всему константу, чтобы все стало неотрицательным и через динамическое программирование, в массиве идти до суммы S+константа
Выложи да полное решение.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.07.2011, 22:30     У покупателя есть n монет достоинством H(1)...H(n) #4
Цитата Сообщение от boom299 Посмотреть сообщение
У покупателя есть n монет достоинством H(1)...H(n). У продавца есть m монет достоинством B(1)...B(l). Может ли купить покупатель вещь стоимостью S так, чтобы у продавца нашлась точная сдача (если она необходима)
Вариант:
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
#include <iostream> 
using namespace std;
int main()
{
    int i, *mas, *mas1, M, N, tmp, S, sum=0, j;
    cout<<"N= ";
    cin>>N;
    mas1=new int[N];
    for(i=0; i<N; i++)
    {
        cout<<"B("<<i+1<<")= ";
        cin>>mas1[i];
        sum+=mas1[i];
    }
    mas=new int[sum+1];
    mas[0]=1;
    for(i=0; i<=sum; i++)
        mas[i]=0;
    for(i=0; i<N; i++)
    {
        for(j=sum-1; j>=0; j--)
            if(mas[j]==1 && j+mas1[i]<=sum)
                mas[j+mas1[i]]=1;
        mas[mas1[i]]=1;
    }
    cout<<"M= ";
    cin>>M;
    for(i=0; i<M; i++)
    {
        cout<<"B("<<i+1<<")= ";
        cin>>tmp;
        for(j=0; j<=sum; j++)
            if(mas[j] && j-tmp>=0)
                mas[j-tmp]=1;
    }
    cout<<"S= ";
    cin>>S;
    if(S<0 || S>sum)
        cout<<"No"<<endl;
    else
        if(mas[S]==0)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    delete [] mas1;
    delete [] mas;
    return 0;
}
Жанерке
 Аватар для Жанерке
34 / 34 / 2
Регистрация: 22.09.2013
Сообщений: 170
15.11.2013, 23:50     У покупателя есть n монет достоинством H(1)...H(n) #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
mas=new int[sum+1];
* * mas[0]=1;
* * for(i=0; i<=sum; i++)
* * * * mas[i]=0;
* * for(i=0; i<N; i++)
* * {
* * * * for(j=sum-1; j>=0; j--)
* * * * * * if(mas[j]==1 && j+mas1[i]<=sum)
* * * * * * * * mas[j+mas1[i]]=1;
* * * * mas[mas1[i]]=1;
* * }
можете объяснить эту часть проги
Yandex
Объявления
15.11.2013, 23:50     У покупателя есть n монет достоинством H(1)...H(n)
Ответ Создать тему
Опции темы

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