<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截圖

## Code

// 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