글 읽기 - DP+비트마스크 문제.

qkqhxla1 7년 전 0

다 잘 나오는것 같은데 왜 틀렸을까요???

#include <iostream>
using namespace std;
int n,m,c,weight[20];
int j[2] = {0,0};
int getmax(int capacity, int index, int jewelry, int count)
{
	int ret = 0;
	if(index==n) //끝까지 갔을때
	{
		if(count > j[0]) //보석 갯수가 현재 j[0]보다 많으면
		{
			j[0] = count;
			j[1] = jewelry;
		}
		return 0;
	}
	int unselected = getmax(capacity, index+1, jewelry, count);
	int selected = 0;
	if(capacity >= weight[index] && !(jewelry & 1<<index)) //용량이 남아있고 해당 보석을 가져가지 않았으면
		selected = getmax(capacity-weight[index], index+1, jewelry | 1<<index, count+1) + 1;
	return max(unselected, selected);
}
int main()
{
	cin>>n>>m>>c;
	for(int i=0;i<n;i++)
		cin>>weight[i];
	int answer = 0;
	for(int i=0;i<m;i++)
	{
		j[0] = 0; //보석 고른 갯수 초기화
		j[1] = j[1]; //고른 보석 목록들은 유지. 
		getmax(c, 0, j[1], 0);
		answer += j[0]; //고른 갯수만큼 답에 더해줌.
	}
	cout<<answer<<endl;
	return 0;    
}

zlzmsrhak 7년 전 1

반례입니다.

백트래킹이지만, 전수조사가 되지 않는 것 같습니다.

한 가방 안에 넣을 수 있는 모든 조합을 계산한 후, DP를 사용하면 될 것 같습니다.

6 2 9
3 4 4 1 3 3

qkqhxla1 7년 전 0

도움 많이 받네요 ㅎㅎ 정말 감사합니다

qkqhxla1 7년 전 0

풀었어요!!! 감사합니다!!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DP+비트마스크 문제.

qkqhxla1 7년 전 0

zlzmsrhak 7년 전 1

qkqhxla1 7년 전 0

qkqhxla1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말