글 읽기 - 뭔가 이상해요.. 근데 왜 이상한지 모르겠어요 ㅠㅠ

iamcaseyda 1년 전 0

재귀를 이용해 브루트포스 방법으로 풀었습니다. 예제를 입력하면 답이 14가 나와야하는데 13이 나옵니다.. 알고리즘은 맞는 것 같은데 어느부분이 잘못됬는지 확인해주실 수 있나요..?

# include <iostream>
# include <queue>
# include <vector>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

int value(vector<int>& solution, vector<int>& weights)
{
	int sum = 0;
	
	for (int i = 0; i < weights.size(); i++)
		sum += (solution[i] * weights[i]);
	
	return sum;
}

void knapsack(vector<int>& weights, vector<int>& values, int k, int i, vector<int>& solution, vector<int>& bestSolution, int& maxProfit)
{
    int profit = value(solution, values);
    
    if (i >= weights.size() || k >= 0)
    {
        if (profit > maxProfit)
        {
            maxProfit = profit;
            bestSolution = solution;
        }
        
        return;
    }
    
    
    if (weights[i] <= k)
    {
        solution[i] = 1;
        knapsack(weights, values, k - weights[i], i + 1, solution, bestSolution, maxProfit);
    }
    else
    {
        solution[i] = 0;
        knapsack(weights, values, k, i + 1, solution, bestSolution, maxProfit);
    }
    
}


int main()
{
    int n, capacity;
    cin >> n >> capacity;
    
    
    vector<int> weights;
    vector<int> values;
    vector<int> solution(n);
    vector<int> bestSolution(n);
    

    
    int maxProfit;
    maxProfit = 0;
     
    for (int i = 0; i < n; i++)
    {
        int weight, value;
        cin >> weight >> value;
        weights.push_back(weight);
        values.push_back(value);
    }
    
    
    
    knapsack(weights, values, capacity, 0, solution, bestSolution, maxProfit);
    
    
    
    cout << maxProfit << endl;
    
    return 0;
}

seawon0808 1년 전 0

무슨 문제인지 알려주세요.

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

문제

문제

출처

ICPC

뭔가 이상해요.. 근데 왜 이상한지 모르겠어요 ㅠㅠ

iamcaseyda 1년 전 0

seawon0808 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말