Jak stworzyc algorytm zachlanny(?) do tego programu

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.

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

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! - Ł

0

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

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

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ć :]

0

ok jeszcze raz wielkie dzieki [browar]

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 :-)

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