#UVa:11450-Wedding shopping

利用 DP 中的背包問題方式變化去解,就是對於每一項本來要放入背包的部分變成每一項有不同重量可以放入,並且要找全部都有放入的情況才是解。

C++(0.000)

/*******************************************************/
/* UVa 11450 Wedding shopping                          */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/03/30                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  int N;
  while(scanf("%d", &N) != EOF){
    for(int caseNumber = 1; caseNumber <= N ; ++caseNumber){
      int M, C;
      scanf("%d%d", &M, &C);

      vector<vector<int>> garmentModels(C + 1);
      for(int i = 1 ; i <= C ; ++i){
        int K;
        scanf("%d", &K);

        garmentModels[i] = vector<int>(K);
        for (int j = 0; j < K; ++j){
          scanf("%d", &garmentModels[i][j]);
        }
      }

      vector<vector<bool>> dp(C + 1, vector<bool>(M + 1, false));
      dp[0][0] = true;
      for (int garmentIndex = 1 ; garmentIndex <= C ; ++garmentIndex){
        for(int space = 0 ; space <= M ; ++space){
          for(int itemIndex = 0 ; itemIndex < garmentModels[garmentIndex].size() ; ++itemIndex){
            if (space - garmentModels[garmentIndex][itemIndex] >= 0 &&
              dp[garmentIndex - 1][space - garmentModels[garmentIndex][itemIndex]]){
              dp[garmentIndex][space] = true;
            }
          }
        }
      }

      bool hasSolution = false;
      for(int space = M ; space >= 0 ; --space){
        if(dp[C][space]){
          printf("%d\n", space);
          hasSolution = true;
          break;
        }
      }

      if(!hasSolution) printf("no solution\n");
    }
  }
  return 0;
}

回應

目前無留言,歡迎留言!

發表迴響

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

%d 位部落客按了讚: