題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b030。
和 b028: 忙碌的超商店員 與 b029: 福袋!福袋!一樣,用 Dynamic Programming 來解。
底下演算法為參考 「演算法筆記的 0/1 Knapsack Problem」 而來的:
- #include <iostream>
- #include <cstring>
- using namespace std;
- int main()
- {
- int n, m;
- cin >> n >> m;
- int v[n], w[m];
- for(int i = 0; i < n; i++)
- {
- cin >> w[i] >> v[i];
- }
- int joy[n+1][m+1];
- memset(joy, 0, sizeof(joy));
- for (int i = 0; i < n; ++i) // 窮舉每部影片
- {
- for (int j = 0; j <= m; ++j)// 窮舉每種長度
- {
- if (j - w[i] < 0)
- // 可觀長度不夠,故只能不看。
- joy[i+1][j] = joy[i][j];
- else
- // 可觀長度足夠,可以看或不看。
- joy[i+1][j] =
- max(
- joy[i][j],
- joy[i][j - w[i]] + v[i]
- );
- }
- }
- cout << joy[n][m] << endl;
- return 0;
- }
沒有留言:
張貼留言