글 읽기 - 반례를 못찾겠어요 ㅠㅠ

pppzppp 4년 전 0

반례부탁드리겠습니다 ㅠㅠ..

d[n] = d[1~n-] + a[i] 로 무게가 넘지않게 구하는 방식입니다.

	#include <iostream>

	using namespace std;

	
	typedef struct item {

		long long weight;
		long long value;
	};
	int  total_weight;
	item d[101];
	item a[101];


	long long go(int n) {
		
		if (a[1].weight <= total_weight) {
			d[1].value = a[1].value;
			d[1].weight = a[1].weight;
		}
		else {
			d[1].value = 0;
			d[1].weight = 0;
		}
		
		for (int i = 2; i <= n; i++) {
			d[i].value = 0;
			d[i].weight = 0;
			for (int j = 1; j < i; j++) {
				if (d[j].weight + a[i].weight > total_weight) {
					if (d[i].value < a[i].value && a[i].weight <= total_weight) {
						d[i].value = a[i].value;
						d[i].weight = a[i].weight;
					}
					
				}
				else {
					if (d[i].value < d[j].value + a[i].value) {
						d[i].value = d[j].value + a[i].value;
						d[i].weight = d[j].weight + a[i].weight;	
					}
					

				}

			}
			
		
			
		}

		long long max = d[1].value;
		for (int i = 2; i <= n; i++) {
			if (max < d[i].value)
				max = d[i].value;
		}
		
		return max;
		
	}

	int main() {

		int n;
		

		cin >> n >> total_weight;

		for (int i = 1; i <= n; i++) {
			cin >> a[i].weight >> a[i].value;
		}
		
		cout << go(n);
		
		return 0;
	}

201812106 4년 전 3

반례입니다

8 4

1 3

1 6

1 3

1 2

1 5

1 8

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

문제

문제

출처

ICPC

반례를 못찾겠어요 ㅠㅠ

pppzppp 4년 전 0

201812106 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말