#UVa:11900-Boiled Eggs

灆洢 2020-05-06 10:53:00

利用 Q 的容量對雞蛋的重量做 0-1 背包問題,得出來可放入 Q 容量的最大雞蛋數後,再與 P 數量取最小值即可。

C++(0.000)

/*******************************************************/
/* UVa 11900 Boiled Eggs                               */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2020/05/06                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int main() {
  int T;
  while (scanf("%d", &T) != EOF) {
    for (int caseNumber = 1 ; caseNumber <= T ; ++caseNumber) {
      int n, P, Q;
      scanf("%d%d%d", &n, &P, &Q);

      vector<int> eggs;
      for (int i = 0 ; i < n ; ++i) {
        int egg;
        scanf("%d", &egg);
        eggs.push_back(egg);
      }

      vector<int> weightDPTable(Q + 1, 0);
      for (int i = 0 ; i < n ; ++i) {
        for (int j = Q ; j >= eggs[i] ; --j) {
          weightDPTable[j] = max(weightDPTable[j], weightDPTable[j - eggs[i]] + 1);
        }
      }

      printf("Case %d: %d\n", caseNumber, min(weightDPTable[Q], P));
    }
  }

  return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料