글 읽기 - 반례를 찾습니다.

2015136077 3년 전 0

간단한 문제인데 못찾겠습니다 ㅠ

count를 통해서 이미 참조한 물건은 참조하지 않았구, 참조한 물품은 push_item에 넣어두었습니다.

반례가 있을까요?

#include <iostream>
#include <vector>
#include <algorithm>

int N, K;
std::vector<int> cost;
std::vector<int> weight;
std::vector<int> dp;
//무게가 i인 값에 들어간 item
std::vector< std::vector<int> > push_item;

//가중치는 다른데 무게는 같을 때 -> 이건 처리해준다.
//무게는 다른데 가중치가 같을 때 -> 이것도 할텐데?
//한번 들어간 item은 다시 넣을 수 없다.
int calculate() {
	int rst = 0;
	for (int i = 1; i <= K; i++) {
		for (int j = 0; j < N; j++) {
			if (i - weight[j] >=0) {
				if (std::count(push_item[i - weight[j]].begin(), push_item[i - weight[j]].end(), j)) {
					push_item[i].push_back(j);
					continue;
				}
				if (dp[i] < dp[i - weight[j]] + cost[j]) {
					dp[i] = dp[i - weight[j]] + cost[j];
					push_item[i] = push_item[i - weight[j]];
					push_item[i].push_back(j);
				}
			}
		}
		rst = std::max(rst, dp[i]);
	}
	return rst;
}


int main() {
	scanf("%d %d", &N, &K);
	dp.assign(K + 1, 0);
	push_item.assign(K + 1, std::vector<int>(0,0));
	for (int i = 0; i < N; i++) {
		int w, v;
		scanf("%d %d", &w, &v);
		weight.push_back(w);
		cost.push_back(v);
	}
	printf("%d", calculate());
}

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

문제

문제

출처

ICPC

반례를 찾습니다.

2015136077 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말