动态规划 资源分配问题C++代码实现

以下是动态规划的资源分配问题的C++代码实现：

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

const int N = 105;
int p[N], f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> p[i];

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int k = 0; k <= i - 1; k ++ )
                f[i][j] = max(f[i][j], f[k][j - 1] + p[i] - p[k + 1]);

    int res = f[n][m];
    cout << res << endl;

    return 0;
}

其中，`p` 数组存储了每个任务所需的资源量，`f[i][j]` 表示前 `i` 个任务分配给 `j` 个人时的最大收益。在代码中，我们先将 `f` 数组初始化为负无穷，然后进行三重循环，枚举任务数量、人数以及最后一个人分配的任务，更新状态转移方程。最后的结果即为 `f[n][m]`。

相关问题

银行家算法c++代码实现

银行家算法（Banker's Algorithm）是一种死锁避免算法，用于避免并发系统中的死锁问题。它由艾德加·沃茨·迪科斯基（Edsger W. Dijkstra）于1965年提出。银行家算法的主要思想是在进程请求资源时，先判断该请求是否会导致系统进入不安全状态，如果不会，则分配资源；否则，让进程等待，直到请求满足安全条件。

以下是银行家算法的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义进程状态
enum ProcessState {
    Ready,      // 就绪
    Running,    // 运行
    Blocked,    // 阻塞
    Dead        // 终止
};

// 定义进程结构体
struct Process {
    int id;                 // 进程ID
    ProcessState state;     // 进程状态
    vector<int> max_res;    // 进程最大需求资源量
    vector<int> need_res;   // 进程还需资源量
    vector<int> allocation_res; // 进程已分配资源量
};

// 定义银行家算法类
class Banker {
private:
    int process_num;        // 进程数量
    int res_num;            // 资源种类数量
    vector<int> available_res;  // 系统可用资源量
    vector<Process> processes;  // 进程列表

public:
    Banker(int pnum, int rnum, vector<int> available, vector<Process> p) : 
            process_num(pnum), res_num(rnum), available_res(available), processes(p) {}

    // 银行家算法判断
    bool isSafe() {
        vector<int> work(available_res.begin(), available_res.end()); // 工作向量
        vector<bool> finish(process_num, false);   // 完成进程标记
        vector<int> safe_sequence;  // 安全序列

        int count = 0;  // 已完成进程数
        while (count < process_num) {
            bool found = false;
            for (int i = 0; i < process_num; ++i) {
                if (finish[i] == false) {
                    bool finishable = true;
                    for (int j = 0; j < res_num; ++j) {
                        if (processes[i].need_res[j] > work[j]) {
                            finishable = false;
                            break;
                        }
                    }
                    if (finishable) {
                        for (int j = 0; j < res_num; ++j) {
                            work[j] += processes[i].allocation_res[j];
                        }
                        finish[i] = true;
                        safe_sequence.push_back(i);
                        found = true;
                        count++;
                    }
                }
            }
            if (found == false) {
                return false;
            }
        }

        cout << "Safe sequence: ";
        for (int i = 0; i < process_num; ++i) {
            cout << "P" << safe_sequence[i];
            if (i != process_num - 1) {
                cout << " -> ";
            }
        }
        cout << endl;

        return true;
    }

    // 进程请求资源
    bool requestRes(int pid, vector<int> request) {
        vector<int> work(available_res.begin(), available_res.end()); // 工作向量
        vector<int> finish(process_num, false);   // 完成进程标记

        // 判断请求是否满足需求
        for (int i = 0; i < res_num; ++i) {
            if (request[i] > processes[pid].need_res[i]) {
                return false;
            }
        }

        // 判断请求是否满足可用资源量
        for (int i = 0; i < res_num; ++i) {
            if (request[i] > available_res[i]) {
                return false;
            }
        }

        // 模拟分配资源
        for (int i = 0; i < res_num; ++i) {
            available_res[i] -= request[i];
            processes[pid].allocation_res[i] += request[i];
            processes[pid].need_res[i] -= request[i];
        }

        // 判断是否会导致系统不安全
        int count = 0;
        while (count < process_num) {
            bool found = false;
            for (int i = 0; i < process_num; ++i) {
                if (finish[i] == false) {
                    bool finishable = true;
                    for (int j = 0; j < res_num; ++j) {
                        if (processes[i].need_res[j] > work[j]) {
                            finishable = false;
                            break;
                        }
                    }
                    if (finishable) {
                        for (int j = 0; j < res_num; ++j) {
                            work[j] += processes[i].allocation_res[j];
                        }
                        finish[i] = true;
                        found = true;
                        count++;
                    }
                }
            }
            if (found == false) {
                // 分配资源后会导致系统不安全，回滚分配
                for (int i = 0; i < res_num; ++i) {
                    available_res[i] += request[i];
                    processes[pid].allocation_res[i] -= request[i];
                    processes[pid].need_res[i] += request[i];
                }
                return false;
            }
        }

        return true;
    }
};

int main()
{
    // 测试数据
    int process_num = 5;
    int res_num = 3;
    vector<int> available_res {3, 3, 2};
    vector<Process> processes {
        {0, Ready, {7, 5, 3}, {7, 5, 3}, {0, 0, 0}},
        {1, Ready, {3, 2, 2}, {3, 2, 2}, {0, 0, 0}},
        {2, Blocked, {9, 0, 2}, {9, 0, 2}, {0, 0, 0}},
        {3, Running, {2, 2, 2}, {2, 2, 2}, {0, 0, 0}},
        {4, Ready, {4, 3, 3}, {4, 3, 3}, {0, 0, 0}}
    };

    // 初始化银行家算法
    Banker banker(process_num, res_num, available_res, processes);

    // 测试安全性
    banker.isSafe();

    // 测试进程请求资源
    int pid = 1;
    vector<int> request {1, 0, 2};
    if (banker.requestRes(pid, request)) {
        cout << "Process P" << pid << " request success!" << endl;
    } else {
        cout << "Process P" << pid << " request failed!" << endl;
    }

    return 0;
}

在上面的代码中，我们定义了一个`Process`结构体来表示进程，包含了进程ID、状态、最大需求资源量、还需资源量和已分配资源量等信息。我们还定义了一个`Banker`类来实现银行家算法，构造函数中需要传入进程数量、资源种类数量、系统可用资源量和进程列表等参数。`isSafe()`函数用于判断系统是否安全，而`requestRes()`函数用于模拟进程请求资源的情况。

ffmpeg 获取 rtsp 视频流 c++ 代码实现

以下是获取 RTSP 视频流并转换为 OpenCV Mat 格式的 C++ 代码示例，需要使用 FFmpeg 库：

#include <opencv2/opencv.hpp>
extern "C" {
#include <libavformat/avformat.h>
#include <libavcodec/avcodec.h>
#include <libswscale/swscale.h>
}

int main(int argc, char* argv[])
{
    AVFormatContext* pFormatCtx = nullptr;
    AVCodecContext* pCodecCtx = nullptr;
    AVCodec* pCodec = nullptr;
    AVFrame* pFrame = nullptr;
    AVPacket* packet = nullptr;
    struct SwsContext* img_convert_ctx = nullptr;

    av_register_all();
    avformat_network_init();

    // 填写 RTSP 地址
    const char* url = "rtsp://example.com/stream";

    if (avformat_open_input(&pFormatCtx, url, nullptr, nullptr) != 0) {
        std::cerr << "Failed to open input stream." << std::endl;
        return -1;
    }

    if (avformat_find_stream_info(pFormatCtx, nullptr) < 0) {
        std::cerr << "Failed to find stream information." << std::endl;
        return -1;
    }

    // 找到视频流
    int videoIndex = -1;
    for (int i = 0; i < pFormatCtx->nb_streams; i++) {
        if (pFormatCtx->streams[i]->codecpar->codec_type == AVMEDIA_TYPE_VIDEO) {
            videoIndex = i;
            break;
        }
    }
    if (videoIndex == -1) {
        std::cerr << "Failed to find video stream." << std::endl;
        return -1;
    }

    // 获取视频解码器
    pCodecCtx = avcodec_alloc_context3(nullptr);
    avcodec_parameters_to_context(pCodecCtx, pFormatCtx->streams[videoIndex]->codecpar);
    pCodec = avcodec_find_decoder(pCodecCtx->codec_id);
    if (pCodec == nullptr) {
        std::cerr << "Failed to find codec." << std::endl;
        return -1;
    }
    if (avcodec_open2(pCodecCtx, pCodec, nullptr) < 0) {
        std::cerr << "Failed to open codec." << std::endl;
        return -1;
    }

    // 分配内存
    pFrame = av_frame_alloc();
    packet = av_packet_alloc();

    // 初始化转换器
    img_convert_ctx = sws_getContext(pCodecCtx->width, pCodecCtx->height, pCodecCtx->pix_fmt,
        pCodecCtx->width, pCodecCtx->height, AV_PIX_FMT_BGR24, SWS_BICUBIC, nullptr, nullptr, nullptr);

    while (av_read_frame(pFormatCtx, packet) >= 0) {
        if (packet->stream_index != videoIndex) {
            av_packet_unref(packet);
            continue;
        }

        // 解码
        int ret = avcodec_send_packet(pCodecCtx, packet);
        if (ret < 0) {
            std::cerr << "Error sending a packet for decoding." << std::endl;
            break;
        }
        while (ret >= 0) {
            ret = avcodec_receive_frame(pCodecCtx, pFrame);
            if (ret == AVERROR(EAGAIN) || ret == AVERROR_EOF) {
                break;
            }
            else if (ret < 0) {
                std::cerr << "Error during decoding." << std::endl;
                break;
            }

            // 转换为 OpenCV Mat 格式
            cv::Mat frame(pFrame->height, pFrame->width, CV_8UC3);
            sws_scale(img_convert_ctx, pFrame->data, pFrame->linesize, 0, pCodecCtx->height,
                frame.data, frame.step);

            // 显示图像
            cv::imshow("Frame", frame);
            cv::waitKey(1);

            av_frame_unref(pFrame);
        }
        av_packet_unref(packet);
    }

    // 释放资源
    av_packet_free(&packet);
    av_frame_free(&pFrame);
    avcodec_close(pCodecCtx);
    avcodec_free_context(&pCodecCtx);
    avformat_close_input(&pFormatCtx);
    sws_freeContext(img_convert_ctx);

    return 0;
}

需要注意的是，该代码示例仅适用于单个 RTSP 视频流的情况。如果需要同时处理多个 RTSP 视频流，需要使用多线程或多进程来实现。