백준 2662번 : 기업투자 - DP 냅색(배낭) 알고리즘 C++

https://www.acmicpc.net/problem/2662

2662번: 기업투자

 

 

1.문제설명

투자액수	1	2	3	4
기업 A에서 받는 이익	5	6	7	8
기업 B에서 받는 이익	1	5	9	15

투자금액 N과 기업의 개수 M이 주어진다.

M개의 기업에 주어진 투자액수를 활용해 최대 이익을 얻어야 한다.

각각 기업은 최대 한번 투자할 수 있고, 투자하지 않아도 된다.

 

A에 4를 투자하고 B에 0을 투자하는 건 가능 하지만

A에 1을 투자하고 또 3을 투자하는 건 불가능 하다.

답으로 각 기업에 투자한 금액과, 얻을 수 있는 이익의 최댓값을 산출해야한다.

 

 

 

 

2. 접근방법[알고리즘]

다이나믹 프로그래밍이자 냅색 문제이다.

표를 만들어 각 투자액수에 대하여 얻을 수 있는 최대 이익을 갱신하면 된다.

 

단 이 문제가 까다로운 건 단순히 최대 이익을 구하는 게 아니라

각 기업에 투자한 금액을 저장해야 한다.

이를 위해 dy테이블을 2차원 배열로 만들어 최대 이익을 갱신할 때마다

각 기업에 투자한 금액 또한 누적했다.

 

[ 최대 이익, A에 투자한 금액, B에 투자한 금액]

투자액수	0	1	2	3	4
기업 A 누적	[0,0,0]	[5,1,0]	[6,2,0]	[7,3,0]	[10,4,0]
기업 B 누적	[0,0,0]	[5,1,0]	[10,1,1]	[14,1,3]	[15,0,4]

 

 

 

점화식

dy 테이블에서 index가 0인 column에 이익 최댓값을 저장하고,

index 1 ~ m 까지 1부터 m번 기업까지에 투자한 액수를 저장한다.

최댓값은 다른 냅색, 배낭 문제처럼

단순히 dy[j][0] = dy[j-k][0] + arr[k][i]; 구할 수 있다.

if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
    dy[j][0] = dy[j - k][0] + arr[k][i];

    for (int t = 1; t <= m; t++) {
        if (t == i) dy[j][i] = k;
        else dy[j][t] = dy[j - k][t];
    }
}

 

 

 

 

 

 

3. 문제풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[301][21], dy[301][21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= 0; j--) {
			for (int k = 0; k <= j; k++) {
				//k는 가격
				if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
					dy[j][0] = dy[j - k][0] + arr[k][i];

					for (int t = 1; t <= m; t++) {
						if (t == i) dy[j][i] = k;
						else dy[j][t] = dy[j - k][t];
					}
				}

			}
		}
	}
	cout << dy[n][0] << '\n';

	for (int i = 1; i <= m; i++) {
		cout << dy[n][i] << ' ';
	}

}