台中女中程式解題系統：b031: 吃到飽餐廳

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b031。
和 b028: 忙碌的超商店員 、 b029: 福袋!福袋!、b030: 隨選視訊一樣，用 Dynamic Programming 來解。

底下演算法為參考 「演算法筆記的 Unbounded Knapsack Problem」 而來的：

程式碼：

1. #include <iostream>  
2. #include <cstring>  
3.   
4. using namespace std;  
5.   
6. int main()  
7. {  
8.     int n, m;  
9.     cin >> n >> m;  
10.   
11.     int v[n], w[m];  
12.   
13.     for(int i = 0; i < n; i++)  
14.     {  
15.         cin >> w[i] >> v[i];  
16.     }  
17.   
18.     int foodCost[m+1];  
19.   
20.     memset(foodCost, 0, sizeof(foodCost));  
21.   
22.     for (int i = 0; i < n; ++i)     // 窮舉每種食物  
23.     {  
24.          for (int j = w[i]; j <= m; ++j)// 窮舉每種食量  
25.          {  
26.              foodCost[j] = max(foodCost[j], foodCost[j - w[i]] + v[i]);  
27.          }  
28.     }  
29.   
30.     cout << foodCost[m] << endl;  
31.   
32.     return 0;  
33. }