글 읽기 - 안녕하세요 코드 반례 질문드립니다.

qlehfdl97 4년 전 0

안녕하세요 질문은 처음이라 혹시나 잘못된 부분있으면 지적 부탁드립니다. 빠르게 수정하겠습니다.

제가 푼 방법은 무게당 최대값만을 저장하면서 완전 탐색하는 방법을 사용했습니다.

cache[j]는 j무게일때 최대의 value로 갱신하며 전체 물건을 돈 후 최대값을 출력하는 방법입니다.

문제의 테스트 케이스 및 질문에 있는 테스트케이스는 모두 확인했습니다.

도움 부탁합니다.

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import java.util.Scanner;
import java.util.StringTokenizer;






public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		//변수
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] weights= new int[n+1];
		int[] values= new int[n+1];
	
		//초기화
		int cache[] = new int[100000001]; //cache[i] = i무게에서 최대의 value
		Arrays.fill(cache, -1);
		for(int i = 1;i<=n;i++)
		{
			st=new StringTokenizer(br.readLine());
			weights[i] = Integer.parseInt(st.nextToken());
			values[i] = Integer.parseInt(st.nextToken());
		}

		
		
		
		
		//계산
		for(int i =1 ; i <=n;i++) 
		{
			for(int j =1 ; j <=k;j++) { //현재 가방 무게당 최대 value
				
				
				if(cache[j] != -1 && (j+weights[i])<=k)
				{
					cache[j+weights[i]] =Math.max(cache[j]+values[i],cache[j+weights[i]]);
				}
			}
			cache[weights[i]] = Math.max(cache[weights[i]], values[i]);
			
		}
	
		
		
		
		//출력
		int answer = 0;
		for(int i = 1;i<=k;i++)
		{
			answer = Math.max(answer, cache[i]);
			
		}
		System.out.println(answer);
		
		
		
	}
	
}

nahwasa 4년 전 1

cache 사이즈를 미리 알 수 있음애도 굳이 100000001 만큼 두어서 비효율적입니다.
아이디어 자체는 맞으시나 구현에서 오류가 하나 있습니다.

44번째줄에서 증가시키시면서 값을 넣으셨는데, 47번줄에서 cache[j] != -1로 판단하셨으므로

그러면 i에 해당하는 물건이 하나만 존재하는게 아니고 엄청나게 많이 존재하게 되는겁니다.

무슨말이냐면 cache[1]이 현재 1이라고 봅시다. w가 1이고 v가 1인 물건을 넣는다고 하면

j가 1이고 cache[1]이 -1이 아니니 cache[2]에 값을 넣겠고,

그다음 j가 증가되고 cache[2]를 보니 또 -1이 아니니 cache[3]에 넣겠고.. 그런식입니다.

동일 물건을 여러번 넣게되는 꼴이 됩니다.

이에 따라 아래와 같은 반례가 있겠네요.

qlehfdl97 4년 전 1

감사합니다. 뒤에서부터 탐색하면서 넣으니까 해결되네요.

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

문제

문제

출처

ICPC

안녕하세요 코드 반례 질문드립니다.

qlehfdl97 4년 전 0

nahwasa 4년 전 1

qlehfdl97 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말