이런 문제가 주어진다면 어떤 알고리즘을 이용하시겠어요?
The Ship Loading Problem
A shipping company has employed you to write a program to determine how it should load its ships to maximise its profits. The company has a large warehouse that contains many containers of cargo. Each container has a weight and a profit associated with it. The company has a fleet of ships, with each ship having a weight limit known as the capacity.
The problem for you is that given the capacity of a single ship, and a list of containers that must be shipped, which containers should be put on which ship to maximise the profit of the journey.
For example, assume the following details were given:
Ship's capacity is 1000 tonnes.
Container 1: weight = 100 tonnes, profit = $10,000
Container 2: weight = 100 tonnes, profit = $5,000
Container 3: weight = 900 tonnes, profit = $20,000
Container 4: weight = 100 tonnes, profit = $5,000
In this case, it would be best to load the ship with containers 1 and 3 as that does not exceed the capacity of the ship, and yields the most profit ($30,000).
It is tempting to use a greedy approach to solving the problem, simply taking containers with the best profit until the ship is full. Unfortunately this does not guarantee an optimal solution in all cases. For example if
Ship's capacity is 1000 tonnes.
Container 1: weight = 1000 tonnes, profit = $10,000
Container 2: weight = 100 tonnes, profit = $9,000
Container 3: weight = 100 tonnes, profit = $9,000
One way of solving the problem to guarantee an optimal solution is to use a brute force search of all possible container combinations. (A less computationally expensive solution is possible using Dynamic Programming - more on that in second year CS!)
Over the next 4 weeks you are to develop an application that will solve the ship loading problem using a brute force search that is both recursive and iterative.
This prac
For this prac you should develop the File I/O section of your application, and become familiar with the problem.
The input to your application will be a text file of ship and container details in the following format.
line 1: Ship name
line 2: Ship's capacity as an integer
line 3: A pair of integers, where the first is the weight of container 1, and the second is the profit of that container.
line 4: A pair of integers, where the first is the weight of container 2, and the second is the profit of that container.
...
line x: A pair of integers, where the first is the weight of container x-2, and the second is the profit of that container.
You should read the file creating a single Ship object, and as many Container objects as required. The Container objects should be stored in an extensible list (for example an ArrayList, Vector or LinkedList) that forms a class field of a class called Solver. A skeleton Solver class is provided.
The name of the file should be passed in as a command line argument to your application. (That is, using the String args[] parameter of main()).
In subsequent pracs you will add methods to Solver for working with the Ship and list of containers you have created.
자동번역알고리듬.. :wink: 죄송합니다. 진지하게 질문하시는데 실
자동번역알고리듬.. :wink:
죄송합니다. 진지하게 질문하시는데 실없는소리를.. :oops:
http://blog.dreamwiz.com/shjii
이거참 해석을 잘 한건지 모르겠네요.내용은 brute force se
이거참 해석을 잘 한건지 모르겠네요.
내용은 brute force search 로 프로그램을 만들면 된다.
다만 I/O 규칙만 이렇게 저렇게 지켜 달라. 라는 내용 맞나요?
다만, 질문하신 분의 의도는 "brute force search 로는 느릴것 같아서 다른 알고리즘은 없나?" 인가요?
맞다면, Ant Colony Optimization Algorithms 이게 좋을 것 같네요.
PS 자동번역 알고리즘에 한표~
CS 숙제죠. "brute force search that is both
CS 숙제죠. "brute force search that is both recursive and iterative"로 풀라고 되었군요. 모든 경우의 컨테이너 조합을 가장 이익이 많이 나는 순을 구하고 차례로 무게가 초과되었으면 다음(차선의 이익)을 읽어가는 식으로 하면 되겠네요.
----
I paint objects as I think them, not as I see them.
atie's minipage
Sorry i can't post in korean here is in school computer lab.
One way of solving the problem to guarantee an optimal solution is to use a brute force search of all possible container combinations
yes.. as you can see as above sentence. one of solution is a brute force search.. but.. i am looking for the other way to sove this problem.
My idear is..
there is two sort lists.
one is sorted by weight -----( A )
Container 1: weight = 100 tonnes, profit = $10,000
Container 2: weight = 200 tonnes, profit = $5,000
Container 4: weight = 400 tonnes, profit = $5,000
Container 3: weight = 900 tonnes, profit = $20,000
and other one is sorted by profit -----( B )
Container 3: weight = 900 tonnes, profit = $20,000
Container 1: weight = 100 tonnes, profit = $10,000
Container 2: weight = 200 tonnes, profit = $5,000
Container 4: weight = 400 tonnes, profit = $5,000
and.. the algorithm should be selecting first list of containers
which is Container 1 and. looking at B's list and selecting first of containers which is Contaniner3 and make sure if u select any containers you have to remove it from both of sorted list.
under condition, the ship can contain max weight is 1000
and find out max profits.
As a result, i can get Container 3 and 1
Thanks your attention !!
devilhero mentioned about "Ant Colony Optimization Algorithms"
Can i get more information on it?
thanks.
Integer programming 문제군요. 숙제는 KLDP에서 묻지도
Integer programming 문제군요. 숙제는 KLDP에서 묻지도, 답하지도 맙시다!
그냥 0-1 Knapsack 문제 아닌가요 ? -_-a
그냥 0-1 Knapsack 문제 아닌가요 ? -_-a
cdpark said this was a homework.. my answer is no!!
yes.. it is a problem of oversae's university
but.. i want to learn about this kind of problem.
To be honest, it is not a homework !!
i think.. this problem is good for programming,,
so,, i want to make a good solution of it..
that's it..
i don't know in Korea Education.. Do they have this kind of problem? who care about it?
i want to indecate about this point.. so that's why i was posting it and.. i want to know u guys idea.. what will be a best solution !!
that's all,,, my idea
Ant Colony Optimization Algorithmsht
Ant Colony Optimization Algorithms
http://www.codeproject.com/cpp/GeneticandAntAlgorithms.asp
댓글 달기