다양한 크기를 가진 물체들을 수레로 옮길 때에, 가능한 최소 횟수로 완료하는 알고리듬 과제입니다. 참여자가 문제에 집중할 수 있도록, 메인코드를 제공하는 까닭에 언어를 python으로 제한했습니다.
물체는 10개이며 각 크기는 1~10의 랜덤값입니다. 수레의 크기는 15입니다. 10000번의 반복된 미션을 통해 총 이동횟수의 합을 출력합니다. 참여자는 아래 코딩예제에서 choose라는 함수를 재정의하여 이동횟수를 최적화하시기 바랍니다.
결과를 올리실 때에는 choose 함수 본문과, 메인코드 실행 시 출력결과를 포함하시면 됩니다. 물론 총 이동숫자가 작을 수록 좋은 알고리듬이겠습니다.
########## 아래 함수 choose 를 사용자가 재정의 #########
# 숫자 리스트 things의 숫자들 중,
# cartsize 크기의 수레에 실을 숫자들을 선택하여 리턴
########################################################
def choose(things, cartsize):
chosen = []
chosen_size = 0
for thing in things:
if chosen_size+thing <= cartsize:
chosen.append(thing)
chosen_size += thing
return chosen
############## 아래 본문은 그대로 재사용 ###################
import random
# total_moves 초기화
total_moves = 0
# 총 10000회 시행
for mission in range(10000):
# 10개의 물건들이 각각 1~10 크기로 무작위 생성됨
things = []
for i in range(10):
things.append(random.randrange(1,11))
# print('미션', mission, ':', things)
# 이것들을 크기 15인 수레로 가능한 적은 회수로 이동
while len(things)>0:
chosen = choose(things, 15)
# print(chosen)
for thing in chosen:
things.remove(thing)
total_moves += 1
print('총 이동:', total_moves)
정답 댓글은 아래와 같은 예로 넣으시면 됩니다.
def choose(things, cartsize):
chosen = []
chosen_size = 0
for thing in things:
if chosen_size+thing <= cartsize:
chosen.append(thing)
chosen_size += thing
return chosen
총 이동: 44834
재귀를 사용해 가능한 한 수레를 꽉꽉 채워넣게 작성해 보았읍니다.
def trim (tar, stack):
ans = [tar, []]
for i in enumerate(stack):
pt = i[0]
thing = i[1]
if thing == tar:
return [0,[thing]]
elif thing < tar:
recur = trim(tar-thing, stack[pt+1:])
if recur [0] == 0:
return [0, [thing]+recur[1]]
else:
if recur[0] < ans[0]:
ans = [recur[0], [thing]+recur[1]]
return ans
def choose (things, cartsize):
things.sort(reverse=True)
return trim(cartsize, things)[1]
총 이동: 42475
본 문제의 출제자입니다. 내용이 좀 어려웠는지, 아님 남의 코드 보시는 것이 부담이었는지.. 보름이 지나도 응모가 없으셔서 기본적인 답을 하나 올립니다.
물건들을 수레에 골라넣기 전에, 크기의 역순으로 정렬만 해놓아도 이동횟수가 많이 줄어듭니다.
def choose(things, cartsize):
things.sort(reverse=True)
chosen = []
chosen_size = 0
for thing in things:
if chosen_size+thing <= cartsize:
chosen.append(thing)
chosen_size += thing
return chosen
총 이동: 42666
using System;
using System.Collections.Generic;
namespace solution1
{
class Program
{
static void Main(string[] args)
{
int total_moves = 0;
Random random = new Random();
for (int mission = 0; mission < 10000; mission++)
{
List<int> things = new List<int>();
for (int i = 0; i < 10; i++)
things.Add(random.Next(1, 10));
while (things.Count > 0)
{
var chosen = choose(things, 15);
for (int j = 0; j < chosen.Count; j++)
things.Remove(chosen[j]);
total_moves += 1;
}
}
Console.WriteLine(" {0}", total_moves);
}
static int maxSum;
private static List<int> choose(List<int> things, int cartsize)
{
maxSum = 0;
List<List<int>> chosen = new List<List<int>>();
things.Sort(new Comparison<int>((n1, n2) => n2.CompareTo(n1)));
dfs(0, 0, things, cartsize, new List<int>(), chosen);
return chosen[0];
}
private static void dfs(int idx, int chosen_size, List<int> things, int cartsize, List<int> list, List<List<int>> chosen)
{
if (idx >= things.Count)
{
if (chosen_size > maxSum)
{
chosen.Clear();
chosen.Add(new List<int>(list));
maxSum = chosen_size;
}
return;
}
for (int i = idx; i < things.Count; i++)
{
if (chosen_size + things[i] <= cartsize)
{
list.Add(things[i]);
dfs(i + 1, chosen_size + things[i], things, cartsize, list, chosen);
list.RemoveAt(list.Count - 1);
}
else
{
if (chosen_size > maxSum)
{
chosen.Clear();
chosen.Add(new List<int>(list));
maxSum = chosen_size;
}
}
}
}
}
}
// 총 이동: 38411
2023年06月26日 20:18
chosen = []
chosen_size = 0
def near_cartsize(idx, s, things, cartsize, curr):
global chosen
global chosen_size
if idx >= len(things):
if chosen_size < s:
chosen = curr.copy()
chosen_size = s
return
for j in range(idx, len(things)):
if s + things[j] <= cartsize:
curr.append(things[j])
s += things[j]
near_cartsize(j+1, s, things, cartsize, curr)
curr.remove(things[j])
s -= things[j]
else:
if chosen_size < s:
chosen = curr.copy()
chosen_size = s
def choose(things, cartsize):
global chosen
global chosen_size
chosen = []
chosen_size = 0
things.sort(reverse=True)
near_cartsize(1, things[0], things, cartsize, [things[0]], )
return chosen
총 이동: 42665
2023年06月27日 19:37
풀이 작성