글 읽기 - 반례 부탁드립니다 ㅠ

spqjf12345 3년 전 0

시간 초과가 나서 memozation이 필요한가보다 !! 하고

dp 2차원 배열을 추가하였습니다. xcode 상에선 정답을 내는데 채점을 하면 처음부터 틀려버리네요 ..

혹시 반례라던지 코드에 대해 피드백 주시면 감사하겠습니다.

//
//  12865_nomal_back.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/09.
//

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;
int N, capacity;
int weight[100001];
int value[1001];
int dp[101][1001];
int Max(int A, int B) { if (A > B) return A; return B; }


// 가져갈 수 있을 때 가져가기, 가져 가지 않을 때
int knap_sack(int pos, int capacity){
    if(pos == N) return 0;
    int result = dp[pos][capacity];
    if(result != -1) return result;

    if(weight[pos] <= capacity){ // 가져갈 수 있을 때
        result = knap_sack(pos + 1, capacity - weight[pos]) + value[pos];
    }
    result = Max(result, knap_sack(pos + 1, capacity));
    dp[pos][capacity] = result;
    return dp[pos][capacity];
}

int main(){
    cin >> N >> capacity;
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < N; i++){
        cin >> weight[i] >> value[i];
    }
    
    cout << knap_sack(0, capacity) << '\n';
    return 0;
}

flappybird 3년 전 1

일단 저렇게 저장을 하면 안됩니다.

한번 dp[__][__]가 정해지면 다시는 바뀌지 않는데, 처음으로 dp[][]가 정해진 값이 최댓값이라는 보장이 없습니다.

저 알고리즘으로 푸는것은 힘들어보입니다

1번째~i번째 물건을 크기가 k인 배낭에 적절히 골라서 담을 때 얻을 수 있는 가치의 최댓값을 i, k에 대해 생각해 보세요.

spqjf12345 3년 전 0

아하 dp 배열에 한번 저장한 값이 최대 값이 아니라는 말에서 이해가 되네요

다시 생각해 보아야겠습니다 답변 감사합니다!

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

문제

문제

출처

ICPC

반례 부탁드립니다 ㅠ

spqjf12345 3년 전 0

flappybird 3년 전 1

spqjf12345 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말