UVa 10465 Homer Simpson(전체 백팩)
3982 단어 home
정해진 시간 내에 시간이 가장 적고 남은 경우 햄버거를 얼마나 먹을 수 있는지를 구한다. 2가지 햄버거가 있는데 각 햄버거를 먹는 데 걸리는 시간은 각각 n, m이다.
아이디어:
다중 가방은 햄버거의 개수를 햄버거의 가치로 바꿔야 한다.햄버거 한 개의 가치는 1이다.
dp[w]w의 가방 용량, 햄버거 최대 몇 개를 채워야 합니다.이 조건에 따라 dp수열은 점차적으로 증가하는 것이 아니다(w1, w2가 가득 차서 w1
#include <cstdio> #include <cstdlib> #include <cstring>
#define max(a,b) (((a) > (b)) ? (a) : (b))
const int MAXN = 10010; int dp[MAXN]; int n, m, t; void complete_pack(int w, int v) { for (int i = w; i <= t; ++i) if (dp[i-w] != -1) dp[i] = max(dp[i], dp[i-w] + v); } int main() { while (scanf("%d %d %d", &n, &m, &t) != EOF) { int w[2]; w[0] = n, w[1] = m; memset(dp, -1, sizeof(dp)); dp[0] = 0; for (int i = 0; i < 2; ++i) complete_pack(w[i], 1); int d = 0; for (int i = t; i > 0; --i) { if (dp[i] != -1) break; ++d; } printf("%d", dp[t-d]); if (d) printf(" %d", d); printf("
"); } return 0; }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
내가 어떻게 집에서 일하는 효율을 높였는지나는 2012년부터 원격 근무를 시작했는데 처음에는 일과 생활의 균형을 유지하는 것이 도전이었다.통상적으로, 이 느낌은 불가능할 뿐만 아니라, 내 하루 종일 시간을 차지할 수도 있다.나는 줄곧 8시간 교대로 일했는데...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.