vva10465 - Homer Simpson(전체 백팩)

1065 단어
제목: 10465 - Homer Simpson(전체 가방)
제목 대의: 어떤 녀석이 버거를 아주 좋아해. 지금 두 종류의 버거가 있어. 그리고 이 두 종류의 버거를 먹을 시간을 주고 지정된 시간 안에 그가 가장 많이 먹을 수 있는 버거의 개수가 얼마냐고 물어봐.만약 다 쓰지 못하면 남은 시간에 물을 가져와 마시도록 하고 물을 마시는 시간을 최대한 짧게 요구한다.
문제풀이 사고방식: 완전 배낭.상태 이동 방정식: dp[t]가 t 시간 내에 가장 많이 먹을 수 있는 버거 수.dp【t + v【i】】 = max (dp【t + v【i】】,dp【t】 + 1).
코드:
#include <cstdio>
#include <cstring>

const int N = 2;
const int maxn = 10000;

int dp[maxn];
int v[N];
int t;

int Max (const int a, const int b) { return a > b? a: b; }

int main () {
	
	while (scanf ("%d%d%d", &v[0], &v[1], &t) != EOF) {

		memset (dp, -1, sizeof (dp));
		dp[0] = 0;
		for (int i = 0; i <= N - 1; i++) {
			for (int j = 0; j <= t - v[i]; j++) {
			
				if (dp[j] != -1)
					dp[j + v[i]] = Max (dp[j + v[i]], dp[j] + 1);			
			}
		}

		int i;
		for (i = t; i >= 0; i--)
			if (dp[i] != -1)
				break;
		printf ("%d", dp[i]);

		if (i != t)
			printf (" %d
", t - i); else printf ("
"); } return 0; }

좋은 웹페이지 즐겨찾기