C++且不使用vector头文件完成：题目描述最厉害的加勒比海盗杰克船长驾驶着他的黑珍珠号海盗船找到了一个装满宝藏的藏宝洞。藏宝洞里面有 NN≤100 堆金币第 i堆金币的总重量和总价值分别是 mivi1≤mivi≤100。黑珍珠号的承重量为 TT≤1000。为了长远发展所以他决定带走尽可能少价值的金币但是他要求必须装满。所有金币都可以随意分割分割完的金币重量价值比也就是单位价值不变。请问杰克船长

思路： 这是一个0-1背包问题，需要使用动态规划来解决。

1. 首先定义一个二维数组dp，dp[i][j]表示前i堆金币中，背包容量为j时的最小总价值。
2. 初始化dp数组，将所有元素初始化为一个较大的值，表示无法达到。
3. 对于第i堆金币，有两种情况：
   • 不取第i堆金币，则dp[i][j] = dp[i-1][j]。
   • 取第i堆金币，则dp[i][j] = dp[i-1][j-mi] + vi。 取两种情况的较小值作为dp[i][j]的值。
4. 最后，dp[N][T]即为所求的答案。

代码实现如下：

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;

int main() {
    int N, T;
    cin >> N >> T;
    int mi[N+1], vi[N+1];
    for (int i = 1; i <= N; i++) {
        cin >> mi[i] >> vi[i];
    }
    
    double dp[N+1][T+1];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= T; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= mi[i]) {
                dp[i][j] = min(dp[i][j], dp[i-1][j-mi[i]] + vi[i]);
            }
        }
    }
    
    cout << fixed << setprecision(2) << dp[N][T] << endl;
    
    return 0;
}

时间复杂度分析： 该算法使用了一个二维数组dp，需要遍历所有的金币堆和背包容量，所以时间复杂度为O(NT)。空间复杂度为O(NT)