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; }

좋은 웹페이지 즐겨찾기