무한 배낭 문제 unbounded knapsack에 대한 또 다른 핵심 고찰(dp[i] = min(dp[i], dp[i-k*w[j]] + k*v[j]) = min(dp[i], dp[i-w[j]] + v[j]))

1. 무한 배낭 문제(unbounded knapsack) 일반적인 배낭 문제는 무게가 제한된 배낭에 특정 물건을 최대 가치로 담는 방법을 찾는 문제인데, 각각의 물건은 최대 하나씩만 담을 수 있다 https://deepdata.tistory.com/474 배낭(Knapsack) 문제, 다이나믹 프로그래밍 해법 배우기1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 wi, 가치가 vi로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건deepdata.tistory.com   근데 각 물건을 무한히 담을 수 있는 경우, 그러한 문제를 unbounded knapsack 무한 배낭 문제라고 부른다  알고보니 이미 ..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2024. 12. 27.
  • textsms

m면체 주사위 n개를 굴려서 나올 수 있는 경우의 수를 구하는 방법

3886번: Expected Allowance (acmicpc.net)  m면체 주사위 n개를 굴려서 나온 숫자의 합에 컷백 k를 뺀 값만큼 지폐를 받는다고 할 때, 받을 수 있는 지폐 수의 기댓값 이때, k 이하의 수가 나온다면 최소 1장은 받는다 예를 들어 6면체 주사위 2개를 굴리면? 가능한 숫자의 합은 1부터 12까지인데 모든 경우의 수는 36가지이고 숫자의 합이 2인 경우의 수는 (1,1)로 1가지 3인 경우의 수는 (1,2), (2,1)로 2가지 4인 경우의 수는 (1,3), (2,2), (3,1)로 3가지 k = 3이면 지폐를 1가지 받는 경우의 수는 숫자의 합이 2, 3, 4 3가지 경우에 가능하다. 따라서 지폐 1가지 받는 경우의 수는 1+2+3 = 6가지  그러면 먼저 m면체 주사위 n..

  • format_list_bulleted 조합론
  • · 2024. 8. 17.
  • textsms

가방이 여러개인 multiple 0-1 knapsack(배낭 문제) 해법 배우기

1. 다중 배낭 문제(multiple 0-1 knapsack) https://atcoder.jp/contests/past202206-open/tasks/past202206_h H - Two KnapsacksAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  각각 무게 제한이 A,B인 2개의 가방이 있다고 하자. 이 2개의 가방에 무게가 W, 가치가 V인 물건을 담고자 한다. 2개의 가방에 담긴 물건 가치 합이 최대가 되도록 하는 방법은? 처음에는... 단순히 무게 제한이 A인 가방에 물건을 담고, 담은 물건은 제외한 다음 무..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2024. 7. 3.
  • textsms

0-1 knapsack 배낭 문제 해법 반드시 알아야하는 디테일(물건을 중복해서 담는 경우)

12865번: 평범한 배낭 (acmicpc.net) 최대 한도 무게가 K로 정해진 가방 1개에 무게가 W이고 가치가 V인 N개의 물건을 담고자 할때, 가치가 최대가 되도록 담고자 한다. 당연히 하나의 물건은 가방에 한번만 담을 수 있다  1. 1차원 배열 DP[i] = 가방에 담긴 물건들의 무게 합이 i일때, 가치의 최댓값 DP[i] = max(DP[i], DP[i-w] + v) dp = [0]*(K+1)for w,v in bag: for i in range(K,-1,-1): if i-w >= 0: dp[i] = max(dp[i], dp[i-w] + v)print(dp[K])  주목할 부분은 무게 i = 0,1,2,3,..,K가 아..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2024. 7. 3.
  • textsms

다이나믹 프로그래밍 테크닉 - 어떤 것을 선택하거나 선택하지 않아서 부분집합을 만드는 방법의 수

1. 문제 1750번: 서로소의 개수 (acmicpc.net) 1750번: 서로소의 개수 예제 1의 경우 가능한 경우의 수는 (2, 3), (4, 3), (2, 4, 3)이다. www.acmicpc.net 2. 풀이 수열에서 어떤 원소는 선택하고 어떤 원소는 선택하지 않아 만든 부분집합의 원소들의 최대공약수가 1이 되는 부분집합의 개수를 구하는 문제 안풀어보면 대단히 어렵다. dp[i][j]를 배열의 i번째 수까지 사용했을때, 최대공약수가 j가 되는 부분집합의 개수라고 정의 원소의 크기는 10만까지니까 최대공약수도 당연히 10만까지 가능할거고 여기서 중요한건 자기 자신만 사용하면 최대공약수는 자기 자신이다 초기화할때는 모든 i = 0,1,2,...,n-1에 대하여 dp[i][s[i]] = 1 이게 무슨말..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2023. 11. 15.
  • textsms

integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

1. 문제 15992번: 1, 2, 3 더하기 7 (acmicpc.net) 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 2. 풀이 저번엔 사용 개수의 제한 없이 합을 n으로 만드는 방법을 배웠다면.. https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 ..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2023. 8. 2.
  • textsms