• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

냅색 알고리즘 질문드립니다.

20.06.17 17:42 작성 조회수 232

1

안녕하세요,

강의에서 문제 유형이 무한 개면 일차원 배열에 앞에서부터 참조해서 구하면 되고, 문제 유형이 1개면 일차원 배열에 뒤에서부터 참조해서 구하면 된다고 하셨는데

만약에 문제 유형이 어떤 문제는 2개 어떤 문제는 5개 이런 식으로 갯수가 주어지면 이런 문제도 일차원 배열로 풀 수 있을까요?

제 머리로는 잘 안풀려서 질문드립니다 ㅜㅜ

답변 1

답변을 작성해보세요.

3

안녕하세요^^

개수가 유한개이면 뒤에서 부터 참조하면 됩니다.

최대점수 구하기 문제를 개수까지 넣은 문제로 바꾸어보면

5 20

11 5 6  //점수, 시간, 개수

25 12 2

15 8 3

6 3 6

7 3 4

라면 답은 11+6+(7*4)=45입니다.

코드구현은 다음과 같습니다. 이런 문제가 저지사이트에 있다면 검증을 해보겠는데, 아마 반례는 없을 겁니다. 해보시고 반례가 있으면 얘기해주세요.

#include<bits/stdc++.h>
using namespace std;
int main() {
	freopen("input.txt", "rt", stdin);
	ios::sync_with_stdio(false);
	int n, m, ps, pt, pc;
	cin>>n>>m;
	vector<int> dy(m+1);
	for(int i=0; i<n; i++){
		cin>>ps>>pt>>pc;
		for(int j=m; j>=pt; j--){
			for(int k=1; k<=pc; k++){
				if(j-pt*k<0) break;
				dy[j]=max(dy[j], dy[j-pt*k]+ps*k);
			}			
		}			
	}
	cout<<dy[m]<<"\n";		
	return 0;
}