글 읽기 - knapsack 알고리즘을 적용하여 문제를 풀었는데 틀렸다고 나옵니다 ㅠㅠ

superm 5년 전 0

제가 어디를 놓친건지 감이 잡히지 않네요 ㅠㅠ

반례좀 부탁드리겠습니다

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int n,k;
int d[100001];  // 가방 용량
int w[101];     // 물건의 무게
int v[101];     // 물건의 가치

void dp(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(w[i] <= j){
                d[j] = max(d[j], d[j-w[i]] + v[i]);
            }
        }
    }
    
    cout << d[k] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }
    
    dp();
    
    return 0;
}

portableangel 5년 전 1

1 2

1 1

답은 1입니다. 지금 코드는 한 물건을 여러 번씩 쓰고 있습니다.

superm 5년 전 0

portableangel 님 !!

덕분에 코드 수정하고 해결했습니다 !! 감사합니당 ㅎ_ㅎ

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

문제

문제

출처

ICPC

knapsack 알고리즘을 적용하여 문제를 풀었는데 틀렸다고 나옵니다 ㅠㅠ

superm 5년 전 0

portableangel 5년 전 1

superm 5년 전 0

portableangel 님 !!

덕분에 코드 수정하고 해결했습니다 !! 감사합니당 ㅎ_ㅎ

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말