Jak stworzyc algorytm zachlanny(?) do tego programu

Odpowiedz Nowy wątek
2005-11-08 21:45
sixty-nine
0

Witam.
Musze napisac algorytm zadania znajdujacego sie ponizej. Wydaje mi sie ze trzeba tu uzyc algorytmu zachlannego ale nie jestem pewien poniewaz dla niektorych danych wejsciowych nie bedzie on chyba optymalny. Bede wdzieczny za jakas pomoc. Nie chodzi mi o to aby ktos napisal mi caly algorytm, tylko abyscie mnie prawidlowo naprowadzili bo szczerze mowiac to nie wiem nawet od czego zaczac :(

Wklejam tresc zadania:

Studenci II roku informatyki zaliczyli pomyślnie sesję zimową i wybierają się na wycieczkę po Europie. Co prawda lotem bliżej, ale na pewno nie taniej, więc jako środek transportu uwzględniają wyłącznie autokar. Spędzą w drodze wiele dni, zatem opłaty za noclegi stanowią poważną część kosztów podróży. Ze względu na bezpieczeństwo podróży każdy autokar jedzie tylko w ciągu dnia i nie może przejechać więcej niż 800 km. Noc na trasie (poza początkiem i końcem) studenci i kierowcy spędzają w hotelach. Oczywiście trzeba podróż zaplanować optymalnie, czyli tak, aby koszt noclegów w ciągu całej wycieczki był jak najmniejsza. Przedsiębiorstwo przewozowe znając potrzebę obniżenia kosztów wycieczki, postanowiło zbadać, czy opłaci się układanie planów podróży tak, aby suma opłat za noclegi była możliwie najniższa, nawet wtedy gdyby to miało przedłużyć podróż. W każdej ofercie jest podana odległość hotelu od początku trasy i cena jednostkowa noclegu. Studenci podróżują tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża tylko raz. Nie ma dwóch hoteli w jednym punkcie, więc każdy hotel może być zidentyfikowany przez jego odległość od początku trasy. Nie planuje się noclegu ani na początku ani na końcu trasy. Liczba osób w autobusie nie zmienia się i wszyscy razem z kierowcą płacą taką samą cenę jednostkową za nocleg w tym samym hotelu. Pojemność hoteli jest na tyle dużą, że wszyscy mogą w nim zanocować. Na każdym odcinku trasy o długości 800 km jest przynajmniej jeden hotel. Zakładamy, że długość trasy jest liczbą całkowitą d<=16000, a liczba hoteli h<=1000.

Pomóż przedsiębiorstwu, pisząc program, który po wczytaniu długości trasy, liczby hoteli oraz oferty hoteli (cena jednego noclegu za jedną osobę) znajduje plan najtańszej podróży, tzn. takiej, której suma opłat za hotele była najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno z najmniejszą liczbą noclegów.

Pozostało 580 znaków

2005-11-09 18:14
QkI
0

Witam
Tak mi jakoś przebija przez myśl że identyczne zadanie lub bardzo podobne było na olimpiadzie informatycznej tylko nie pamiętam którego roku :D. Pościągaj sobie niebieskie książeczki tam są rozwiązania zadań z obszernym wyjaśnieniem. Powinno pomóc.

Pozdro

Pozostało 580 znaków

2005-11-11 00:44
0

Przecież to jest zwykły problem wyszukiwania najkrótszej ścieżki w grafie skierowanym ;P
Graf wygląda tak:
Początek to początek trasy :]
Koniec to cel :P

A <ort>wieszkołkami </ort>niech będą <ort>poszczegulne </ort>hotele z tym, że wagi krawędzi wychodzących z wierzchołka oznaczają cenę noclegu w danym hotelu.

Każdy <ort>wieżchołek </ort>jest połączony z tymi które oznaczają hotele znajdujące się w odległości <= 800km i są bliżej celu niż on sam.

Teraz wystarczy zastosować algorytm Digstry i masz optymalne rozwiązanie :)

// słownik! - Ł


<font color="darkblue"><font size="5">セボ</span>
Java PHP SQL
MatLab C# C++ Prolog SIOD</span>
<font size="1">Dziwne jest to, że na większość zadanych tu pytań sam sobię odpowiadam :]</span>

Pozostało 580 znaków

2005-11-13 19:20
sixty-nine
0

ok dzieki za podpowiedz, jutro sie tym sprobuje zajac;)

Pozostało 580 znaków

2005-11-15 18:32
sixty-nine
0

Sebo-dzieki bardzo mi pomogles, programik dziala az milo:) moglbys jeszcze rzucic okiem na to zadanko:

Dana jest tabliczka czekolady złożona z m x n cząstek. Czekoladę należy połamać na pojedyncze cząstki. Kawałki czekolady możemy złamać wzdłuż pionowych i poziomych linii (zaznaczonych na rysunku liniami przerywanymi) wyznaczających podział czekolady na cząstki. Jedno przełamanie kawałka czekolady wzdłuż wybranej pionowej lub poziomej linii dzieli ten kawałek na dwa mniejsze. Każde przełamanie kawałka czekolady jest obarczone pewnym kosztem wyrażającym się dodatnią liczbą całkowitą. Koszt ten nie zależy od wielkości łamanego kawałka, a jedynie od linii wzdłuż której łamiemy. Oznaczmy koszty łamania wzdłuż kolejnych pionowych linii przez x1, x2, . . . , xm-1, a wzdłuż poziomych linii przez y1, y2, . . . , yn-1. Koszt połamania całej tabliczki na pojedyncze cząstki to suma kosztów kolejnych przełamań. Należy obliczyć minimalny koszt połamania całej tabliczki na pojedyncze cząstki

user image

Przykładowo, jeżeli połamiemy czekoladę przedstawioną na rysunku, najpierw wzdłuż linii poziomych, a następnie każdy z otrzymanych kawałków wzdłuż linii pionowych, to koszt takiego połamania wyniesie y1 +y2 +y3 +4 ( x1 +x2 +x3 +x4 +x5). Napisz program, który: wczyta liczby x1, x2, ... , xm-1 i y1, y2, ..., yn-1, obliczy minimalny koszt połamania całej tabliczki na pojedyncze cząstki. Zakładamy, że rozmiary tabliczki czekolady m i n spełniające warunek 2 ? m, n ? 1 000 . Koszty złamań pionowych, liczby x1, x2, . . . , xm-1, są całkowite i spełniają nierówność: 1 ? xi ? 1 000. Koszty złamań poziomych, liczby y1, y2, . . . , yn-1 to też wartości całkowite takie, że 1 ? yi ? 1 000 . Wynikiem działania programu ma być minimalny koszt połamania całej tabliczki na pojedyncze cząstki.

Przykład

Dane: rozmiary tabliczki czekolady: m = 6, n = 4, koszty łamań pionowych: 2, 1, 3, 1, 4, koszty łamań poziomych: 4, 1, 2

Wynik: 42

Pozostało 580 znaków

2005-11-16 01:12
0

Tu to chyba najlepsza będzie metoda zachłanna - czyli najpierw łamiemy wzdłuż krawędzi które mają większą wagę :-/

k=[k1 k2 k3 ... kc]%wagi poszczególnych krawędzi pionowych
K=[K1;K2;K3;...;Km]%wagi poszczególnych krawędzi poziomych
p=[k K';k.*0-1/2 K*0+1/2];
[i,I]=sort(p(1,:));
x=0;%tu zapiszemy minimalny koszt połamania całej tabliczki
f=[1 1];
for i=I
 x=x+p(1,i)*f(1+(p(2,i)>0));
 f=f+p(2,i)*[1 -1]+[1/2 1/2];
end

Nie testowałem ale powinno działać :]


<font color="darkblue"><font size="5">セボ</span>
Java PHP SQL
MatLab C# C++ Prolog SIOD</span>
<font size="1">Dziwne jest to, że na większość zadanych tu pytań sam sobię odpowiadam :]</span>

Pozostało 580 znaków

2005-11-16 16:34
sixty-nine
0

ok jeszcze raz wielkie dzieki [browar]

Pozostało 580 znaków

2005-11-20 23:46
0

czekolada była na OI, polecam rozwiązanie w czasie... uwaga uwaga... stałym! - mnie to zaskoczyło jak je robiłem i dlatego lubie to zadanie bardzo :-)


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0