---
# System prepended metadata

title: Unbounded knapsack problem 結報
tags: [Algorithm_Lab]

---

<style>
    html, body, .ui-content {
    background: #222222;
    color: #00BFFF;
}
::-webkit-scrollbar {
    width: 10px;
}
::-webkit-scrollbar-track {
    background: transparent;
}
::-webkit-scrollbar-thumb {
    background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
    border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
    background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
    /* 設定 code 模板 */
    .markdown-body code,
.markdown-body tt {
    background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
    color: #ddd;
    background-color: #00000036;
}
.hljs-tag {
    color: #ddd;
}
.token.operator {
  background-color: transparent;
}
   
</style>
###### tags: `Algorithm_Lab`

# Unbounded knapsack problem 結報
## OJ AC截圖
![](https://hackmd.io/_uploads/BJI9i1prn.png)

## Code
```cpp=
// UVA 10465
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, t;
    while (cin >> m >> n >> t) {
        vector<int> dp(t + 1, 0);
        if (m <= t) dp[m] = 1;
        if (n <= t) dp[n] = 1;
        for (int i = min(m, n); i <= t; ++i) {
            if (dp[i - n] && i >= n)
                dp[i] = dp[i - n] + 1;
            if (dp[i - m] && i >= m)
                dp[i] = max(dp[i - m] + 1, dp[i]);
        }
        int temp = t;
        while (temp > 0 && !dp[temp]) --temp;
        cout << dp[temp];
        if (temp != t) cout << " " << t - temp;
        cout << endl;
    }
}
```
### $t$ is the time
## 空間複雜度分析
* dp(t + 1) 
* $O(t)$

## 時間複雜度分析
### Best Case
* min(n, m)和t相同
* $O(1)$
### Worst Case
* 走訪dp => t 次
* $O(t)$

## DATE
2023/05/25