212. 앱

백준

1. 냅색 알고리즘

참고

n, m = map(int, input().split())
blist = [0] 
clist = [0]
blist.extend(map(int, input().split())) #byte
clist.extend(map(int, input().split())) #cost
dp = [[0 for _ in range(sum(clist)+1)] for _ in range(n + 1)] #냅색알고리즘이 실행될 dp
result = sum(clist) #열의 최댓값

for i in range(1, n + 1):
    byte = blist[i]
    cost = clist[i]
    
    for j in range(1, sum(clist) + 1):
        if j < cost: #현재 앱을 비활성화할만큼의 cost가 충분하지 않을 경우
            dp[i][j] = dp[i-1][j]
        else:
        	#같은 cost 내에서 현재 앱을 끈 뒤의 byte와 현재 앱을 끄지 않은 뒤의 byte를 비교
            dp[i][j] = max(byte + dp[i-1][j-cost], dp[i-1][j])
            
        if dp[i][j] >= m: #조건이 충족된다면
            result = min(result, j) #더 작은 cost값으로 갱신
if m != 0:
    print(result)
else:
    print(0)

• dp[i][j]는 i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 byte를 의미한다.

  1) 행은 app 개수만큼, 열은 sum(cost)만큼 만들어준다.

  2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.

  3-0) 현재 앱의 cost가 j보다 클 경우 끄지 못하므로 활성화시켜둔다.

  dp[i][j] = dp[i-1][j]

  3-1) 그렇지 않다면 현재 앱을 끈 뒤의 byte와 그렇지 않을 경우의 byte중 큰 값을 dp에 입력한다.

  dp[i][j] = max(byte + dp[i-1][j-cost], dp[i-1][j])

  4) 현재 dp[i][j] 값이 M이상이라면 현재 cost, j와 이전의 result와 비교해 더 작은 값을 취해준다.

  result = min(result, j)

2. C++

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int m[101] = { 0, };
int c[101] = { 0, };
int dp[101][10001] = { 0, };
int result = 1000000000;


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++){
		cin >> m[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> c[i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 10000; j++) {
			if (c[i] <= j)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i]);
			else
				dp[i][j] = dp[i - 1][j];

			if (dp[i][j] >= M) result = min(result, j);
		}
	}
	

	cout << result << endl;

	return 0;
}



출처: https://gusdnr69.tistory.com/155