[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Учебный процесс ГГУ/СШ 27 ->Программирование 1 курс (ПОИТ, ПМ) 1, 2, 3, ... 12, 13, 14
Автор Сообщение
Илья Истомин

Темы: 1
Сообщений: 50

Мой профиль
UPD, 30/12/2015 Долинский М.С.
Обучение\Индивидуальные задания (в форуме)\Динамическое программирование\09_FebG - "Stock Market" 81744
http://dl.gsu.by/task.jsp?nid=1476830&cid=973
 


Решал задачу динамически. Изначально известно, что в день 1 у нас есть K денег
и стоимости различных акций в каждый день. Идея №1 состоит в том, что стоимости
акций в дени D1, и D2 можно рассматривать как способы "превращения" денег дня D1
в деньги дня D2. А зная, кроме того, кол-во денег в день D1 можно посчитать
максимальное кол-во денег, которые можно получить в день D2. Это есть задача о
рюкзаке. Таким обрзом данного условия достаточно чтобы "добраться" до N-го дня.
Но подзадачу о рюкзаке нужно еще каким-то образом решить. Я знаю 2 способа: жадно
(быстро, но не точно) и динамически(точно, но работает за
K(денег)*M(видов предметов)). Результат нужен как можно более точный, а времени
на динамический просчет всей суммы времени нет, поэтому я скомбинировал методы.
Я набирал акции с максимальным коофициэнтом(получил/отдал) пока не остовалось
55000 или меньше. Остальную сумму я считал динамически. Это идея №2. 55000 - это,
кол-во денег, которое можно считать динамически чтобы хватало времени. Вычислил так
X<=30000000/(D*M)
30000000 - примерное кол-во операций выполняемых за 3с
D - максимальное кол-во дней
M - максимальное кол-во акций

#include <bits/stdc++.h>
using namespace std;

int DPMas[70000];
//массив для динамического решения рюкзака

void GreedWay(int n, int *Sum1, int *Sum2, int *p1, int *p2, int Lim){
    int i, BestP1, BestP2, KolIn;
    double BestRation=0, bp1, bp2;
    for(i=1; i<=n; i++){
        bp1=p1[i];
        bp2=p2[i];
        if(BestRation<bp2/bp1){
            BestRation=bp2/bp1;
            BestP1=p1[i];
            BestP2=p2[i];
        }
    }
    KolIn=(Sum1[0]-Lim)/BestP1+1;
    Sum1[0]-=BestP1*KolIn;
    Sum2[0]+=BestP2*KolIn;
}
// процедура для жадного заполнения рюкзака(заполняе до состояния, когда в
// в рюкзаке остается не более чем Lim свободного места)

int DPWay(int m, int n, int *p1, int *p2){
    int i,j;
    for(i=0; i<=n; i++) DPMas[i]=0;
    for(i=0; i<n; i++)
        for(j=1; j<=m; j++)
            if(i+p1[j]<=n && DPMas[i+p1[j]]<DPMas[i]+p2[j])
                            DPMas[i+p1[j]]=DPMas[i]+p2[j];
    return DPMas[n];
}
// динамическое заполнение рюкзака

int BagTask(int CoWays, int Money1, int *price1, int *price2, int DPMax){
    int ans=0;
    if(DPMax<Money1) GreedWay(CoWays, &Money1, &ans, price1, price2, DPMax);
    ans+=DPWay(CoWays, Money1, price1, price2);
    return ans;
}
//решение задачи о рюкзаке комбинированным методом

int main(){
    freopen("stock.in","r",stdin);
    freopen("stock.out","w",stdout);

    int i,j,n,m,k,forecast[20][100],
        DPMas[11]={0,0,0,0,0,0,0,0,0,0,0};

    cin >>m >>n >>k;
    for(j=1; j<=m; j++)
        for(i=1; i<=n; i++) cin >>forecast[i][j];
// ввод прогноза цен на M акций в N ближайших дней, и стартовое кол-во денег

    m++;
    for(i=1; i<=n; i++) forecast[i][m]=1;
// добавление прогноза для еще одной акциии на N дней, которая неизменно стоит 1ед(это
// для того чтобы не описывать алгоритмически возможность не покупать акции, хранить деньгами)

    DPMas[1]=k;
    for(i=2; i<=n; i++) DPMas[i]=BagTask(m,DPMas[i-1],forecast[i-1],forecast[i],55000);
//динамическое вычисление максимальной суммы для каждого дня

    cout <<DPMas[n];
// вывод лучшей суммы в N-й день
}

Михаил Долинский

Темы: 1374
Сообщений: 32487

Мой профиль
+40 бонусов(145->185) за описание решения двух задач на ДП.
Замечание - ссылку на задачу забыл сделать для второй задачи.
Павел Голуб

Темы: 5
Сообщений: 120

Мой профиль


Илья Истомин:

Результат нужен как можно более точный, а времени
на динамический просчет всей суммы времени нет, поэтому я скомбинировал методы.
 


Поспорим?
Тем более 3 секунды, сложность 500к (из условия) *50 * 10 ~ 250kk с головой.


Более того, алгоритм НЕВЕРЕН.

Тест

2 2 104700
347 694
349 698

Ожидаемый ответ 209400 = 300 раз взять 2 акцию (300*349 = 104700 698*300 = 209400)
Полученный 209399



в http://dl.gsu.by/task.jsp?nid=774738&cid=996 можно (и нужно бы обойтись без кучи, и да в С++ есть STL куча)
Максим Грищенко

Темы: 0
Сообщений: 41

Мой профиль
http://dl.gsu.by/task.jsp?nid=1488710&cid=973

program v1;
Var
  a : array[1..100,1..100] of longint;
  b : array[1..100] of longint;
  x1,x2,x3,y1,y2,y3,d1,d2,d3,x4,y4,xf,yf,r1,r2,r,xs,ys,k  : real;
  i,n,m,j,l,s : longint;
  p : string;
  c : char;
Begin
  readln(n);
  readln(m);
  readln(s);
  writeln(n*m*s*4);
end.


1)Так как m чашек это половина ковша мы должны умножить кол-во чашек на 2.
2)Так как n ковшов это половина ведра то мы должны умножить кол-во ковшов на 2.
3)Чтобы найти кол-во чашек нужно перемножить получившееся на кол-во вёдер.
Михаил Долинский

Темы: 1374
Сообщений: 32487

Мой профиль
Принято. Тема - исследование.
+5 бонусов (0->5) за описание решения задачи.

Замечание:
Выложенный исходник надо было почистить от всего лишнего.
Юрий Шишков

Темы: 5
Сообщений: 6

Мой профиль
http://dl.gsu.by/task.jsp?nid=1573225&cid=19

Имеется N (1 <= N <= 400) последовательно пронумерованных от 1 до N
кругов с центром на целой решетке
(0 <= X_i <= 10,000; 0 <= Y_i <= 10,000) и целым радиусом R_i (1 <= R_i <= 500).

Для каждого круга подсчитайте количество других кругов, которые
пересекаются с данным.

Например, рассмотрим 6 кругов и их координаты и радиус.



Формат ввода


* Строка 1: Одно целое число: N
* Строки 2..N+1: Три разделенных пробелами целых числа: X_i, Y_i, R_i

Формат вывода

* Строки 1..N: Строка i содержит одно целое число
- количество других кругов, которые пересекаются с данным кругом.

Пример ввода
6
7 7 7
16 14 7
11 13 2
10 17 3
29 8 5
15 7 4

Пример вывода
3
4
3
2
0
2

Что не так я не могу понять , но помоему всё хорошо ,помогите пожалуйста!!!

var x,y: array [1..10000] of integer;
r: array [1..500] of integer;
i,n,j,kol: integer; s:real;
begin
kol:=0;
readln(n);
for i:=1 to n do readln(x[i],y[i],r[i]);
for i := 1 to n do
begin
for j := 1 to n do
begin
s:=sqrt(sqr(x[j]-x[i])+sqr(y[j]-y[i]));
if s-r[i]<r[j]
then inc(kol);

end;
writeln(kol); kol:=0;
end;
end.
 
Индекс форума ->Учебный процесс ГГУ/СШ 27 ->Программирование 1 курс (ПОИТ, ПМ) 1, 2, 3, ... 12, 13, 14
Time:0,046