본문 바로가기
반응형

SWE326

배낭 문제(Knapsack Problem) - Bounded Knapsack Bounded Knapsack Problem: 물건의 갯수가 제한적일 때(유한할 때) N kg 을 채우는 최대 금액의 방법? 참고 구현 코드- 이 분은 java로 구현했고, array 를 만들지 않고 재귀적으로 함수를 타고 들어가서 반환하는 방식으로 구현하였다.https://blog.naver.com/mycho/220725983486 2018. 12. 9.
배낭 문제(Knapsack Problem) - 0-1 Knapsack Review 냅색 문제는 물건 개수에 따라 3가지 종류가 있다.1) Unbounded Knapsack Problem : 물건의 개수가 무제한일 때2) 0-1 Knapsack Problem : 물건의 개수가 1개뿐일 때 ( 각 종류의 물건을 한 번만 사용할 수 있다. )3) Bounded Knapsack Problem : 물건의 개수가 제한적일 때 ( A물건은 3개, B물건은 5개, ... ) 1번 Unbounded Knapsack Problem은 이전 게시물에서 작성했고이번에는 0-1 Knapsack Problem에 대해 공부할 것이다. 예제 문제 Q. 배낭에 담을 수 있는 물건의 종류와 무게, 가격이 다음과 같다고 가정할 때,배낭 최대 수용 무게 4kg에 담을 수 있는 최대 금액은? 0-1 Knapsa.. 2018. 12. 9.
[성실코딩 31일차] 백준 #1699 제곱수의 합 ** / Knapsack 기말고사 시험공부 겸 Unbounded Knapsack문제를 찾아서 풀었다. 잘못된 접근 방식으로 풀어서 시간초과가 나왔고 ( 예제도 맞고 틀린 방법은 아니라고 생각함! 오래걸려서 비효율적일 뿐,,,,,)그래서 맞은 사람 코드를 보고 공부했다. 옳은 풀이법 및 코드참고 코드 링크 : http://wootool.tistory.com/102이 코드에서 핵심 알고리즘 for (int n = 1; n #include // malloc #include // memset #define INF 987654321 int N; // 문제 자연수 N int square[1000] = { 0, }; // 제곱수 저장해 놓는 배열. // 사이즈 1000 _N) { break; }.. 2018. 12. 9.
[성실코딩 30일차] 백준 #1562 계단 수 ** 모르겠다... 규칙성 있을 것 같은데... 예를 들어, N=14일 경우, "9~0"을 순서대로 놓는 10개를 제외하고, 4개를 정렬하는 경우의 수를 따졌다. 1) "9~0" _ _ _ _ 2) _ _ _ _ "9~0" 3) _ _ _ "9~0" _ 4) _ _ "9~0" _ _ 5) _ "9~0" _ _ _ 이렇게 놓는 방법을 생각했고, 각각 6개, 6개, 3개, 3개, 4개가 가능하다. 그리고 4개 자리 수에서 5개 자리 수로 증가할 때마다, 4개에 수에서 각각 2가지 경우가 추가로 가능하다. ( 끝자리 수인 0이나 9를 제외하고) 왜냐하면 예를들어 마지막 자리수가 4로 끝날 경우, 그 뒤에 값을 추가해주려고 하면 ( _ _ _ 4 ), 3혹은 5가 가능하기 때문. ( _ _ _ 4 5, _ _ _ 4.. 2018. 12. 5.
반응형

티스토리툴바