用数组模拟栈实现递归函数模拟

做算法课设时候看到题目要求模拟函数递归时候栈的入栈出栈过程。本来想着直接调用系统递归函数即可，可是发现系统函数栈的空间非常小大约只有3000层，很容易爆栈。于是便有了用栈去模拟递归函数的想法，但是上网查了下貌似相关代码比较少，让GPT写的代码又牛头不对马嘴，于是手搓了一下。用栈模拟递归的过程，对递归过程，栈的理解都很有帮助。

在这里插入图片描述

二分递归函数模拟

第一个函数erfen为正常的二分递归函数，但是系统的递归栈最多能递归到3000层左右，太少了。我们可以用栈来模拟函数递归的过程，这样栈的层数可以达到我们设置的数组大小，我这里设置了二十万。

#include <iostream>

using namespace std;

const int N = 2e5 + 5;

struct binaryFrame {
    int l, r;
    int level;//记录当前层数
    int step;//记录步数
}stackBinary[N];

/*需要模拟的二分递归函数
int erfen(int arr[], int l, int r, int key)
{
    int ans = -1;


    int mid = l + r >> 1;

    if (arr[mid] == key && l == r) return r;

    if (l >= r) return -1;
    if (arr[mid] >= key) {
        ans = erfen(arr, l, mid, key);
    }
    else {
        ans = erfen(arr, mid + 1, r, key);
    }

    return ans;
}
*/

void binarySearch(int arr[], int l, int r, int key, int& index)
{
    int nowLevel = 1, nowStep = 0, tt = 0, L = l, R = r;
    tt++;
    stackBinary[tt] = { l,r,nowLevel,nowStep };
    cout << "压栈：" << "当前执行函数纸带范围为：(" << L << " , " << R << " )" << " 层数为" << nowLevel << " 执行步数为" << nowStep << "\n";
    while (L < R)
    {
        int mid = L + R >> 1;
        if (arr[mid] >= key)
        {
            R = mid;
            stackBinary[++tt] = { L,R,++nowLevel,++nowStep };
            cout << "压栈：" << "当前执行函数纸带范围为：(" << L << " , " << R << " )" << " 层数为" << nowLevel << " 执行步数为" << nowStep << "\n";
        }
        else {
            L = mid + 1;
            stackBinary[++tt] = { L,R,++nowLevel,++nowStep };
            cout << "压栈：" << "当前执行函数纸带范围为：(" << L << " , " << R << " )" << " 层数为" << nowLevel << " 执行步数为" << nowStep << "\n";
        }
    }
    if (arr[R] == key) {
        index = R;
    }

    while (tt > 0)
    {
        cout << "出栈：" << "当前执行函数纸带范围为：(" << stackBinary[tt].l << " , " << stackBinary[tt].r << " )" << " 层数为" << stackBinary[tt].level << " 执行步数为" << stackBinary[tt].step << "\n";
        tt--;
    }

}


int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int n = 10;
    int key = 2;
    int index = -1;
    binarySearch(arr, 0, n - 1, key, index);
    if (index == -1) {
        cout << "找不到这个吊数\n";
    }
    else {
        cout << "这个B数在数组中的第" << index + 1 << "个位置" << "\n";
    }

    return 0;
}

显示压栈出栈过程
在这里插入图片描述

栈模拟回溯法解决01背包

#include<iostream>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

/*
// 全局变量用于存储最终结果
int max_value = 0;
vector<int> best_set;

/*
// 需要模拟的递归回溯函数
void knapsack(int index, int current_weight, int current_value, int capacity, const vector<int>& weights, const vector<int>& values, vector<int>& chosen_items) {
	// 基础情况：如果考虑完所有物品
	if (index == weights.size()) {
		// 检查当前物品集合是否是一个有效解
		if (current_weight <= capacity && current_value > max_value) {
			max_value = current_value;
			best_set = chosen_items;
		}
		return;
	}

	// 选择当前物品
	chosen_items.push_back(index);
	knapsack(index + 1, current_weight + weights[index], current_value + values[index], capacity, weights, values, chosen_items);
	chosen_items.pop_back(); // 回溯

	// 不选择当前物品
	knapsack(index + 1, current_weight, current_value, capacity, weights, values, chosen_items);
}*/


struct backFrame
{
	int index;
	int current_weight;
	int current_value;
	int step;
	vector<int> chosenItems;
	int stage;
}stackBack[N];

void backBag(int n, int capacity, int& max_value, vector<int>& weights, vector<int>& values, vector<int>& chosenItems, vector<int>& best_set)
{
	int tt = 0, nowStep = 0;
	stackBack[++tt] = { 0,0,0,0,{},0 };
	cout << "压栈：初始化压栈，压入 0 0 0 0 {} 0" << "\n";

	while (tt > 0)
	{
		backFrame now = stackBack[tt];
		cout << "当前执行函数层为：" << now.index << " " << now.current_weight << " " << now.current_value << " " << now.step << "\n";
		if (stackBack[tt].index >= n) {
			if (stackBack[tt].current_value > max_value && stackBack[tt].current_weight <= capacity)
			{
				max_value = stackBack[tt].current_value;
				best_set = stackBack[tt].chosenItems;
				cout << "更新best_set ";
				for (auto i : best_set) cout << i + 1 << " ";
				cout << "\n";
			}
			
			tt--;
			cout << "出栈1：" << now.index  << " " << now.current_weight<< " " << now.current_value << " " << now.step << "\n";
			continue;
		}

		

		if (now.stage == 0) {//栈顶为初始状态的话直接下一层函数压栈
			chosenItems.push_back(now.index);
			stackBack[++tt] = { now.index + 1,now.current_weight + weights[now.index],now.current_value + values[now.index],now.step + 1,chosenItems,0 };
			cout << "压栈1: " << now.index + 1 << " " << now.current_weight + weights[now.index] << " " << now.current_value + values[now.index] << " " << now.step + 1 << "\n";
			
			stackBack[tt - 1].stage ++;
		}
		else if (now.stage == 1) {
            chosenItems.pop_back();
			stackBack[++tt] = { now.index + 1,now.current_weight,now.current_value,now.step + 1,chosenItems,0 };
			cout << "压栈2: " << now.index + 1 << " " << now.current_weight << " " << now.current_value  << " " << now.step + 1 << "\n";
			stackBack[tt - 1].stage ++;
		}
		else if (now.stage == 2) {
			tt--;
			cout << "出栈2：" << now.index  << " " << now.current_weight<< " " << now.current_value << " " << now.step << "\n";
		}

	}

}

int main()
{
	vector<int> weights = { 1,2,3,5,7,6 };
	vector<int> values = { 6,5,10,30,15,25 };
	vector<int> chosenItems;
	vector<int> best_set;
	int capacity = 10, n = 6;
	int max_value = -1;
	/*
	cout << "请输入物品件数和背包容量\n";
	cin >> n >> capacity;
	cout << "请输入" << n << "件物品,每件物品的质量，价值\n";
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		weights.push_back(x);
		values.push_back(y);
	}*/

	backBag(n, capacity, max_value, weights, values, chosenItems, best_set);

	LL sum = 0;

	for (auto i : best_set)
	{
		cout << "选择了第" << i + 1 << "件物品\n";
		sum += weights[i];
	}
	cout << "可以获得的最大价值为" << max_value << "\n";
	cout << "所占用的背包空间为" << sum << "\n";

	return 0;
}

/*
6 10
1 6
2 5
3 10
5 30
7 15
6 25
*/

在这里插入图片描述

栈模拟备忘录法解决01背包

#include <iostream>
#include <vector>
#include <cstring>
#include<Windows.h>

using namespace std;

const int N = 2e4 + 5;


int n, W;

int dp[505][1005]; // 备忘录数组
vector<int> weights;
vector<int> values;

/*需要模拟的备忘录递归函数
// 递归函数，包含备忘录算法逻辑，改为void类型
void knapsack(int idx, int W, int N, int& maxVal) {
    // 基本情况
    if (idx == N || W == 0) {
        maxVal = 0;
        cout << "边界：" << idx << " " << W << " " << maxVal << "\n";
        return;
    }
    // 检查是否已经计算过
    if (dp[idx][W] != -1) {
        maxVal = dp[idx][W];
        cout << "已经计算过：" << idx << " " << W << " " << maxVal << "\n";
        return;
    }
    // 选择不包含当前物品
    knapsack(idx + 1, W, N, maxVal);
    int without = maxVal; // 从上一次递归中获取结果
    cout << "without:" << idx << " " << W << " " << without << "\n";

    int with = 0;
    // 选择包含当前物品，如果背包容量足够
    if (W >= weight[idx]) {
        knapsack(idx + 1, W - weight[idx], N, with);
        with = values[idx] + with; // 添加当前物品的价值
        cout << "with:" << idx << " " << W << " " << with << "\n";
    }

    // 计算最大价值并存储备忘录结果
    maxVal = max(without, with);
    dp[idx][W] = maxVal; // 存储备忘录结果
    //cout<<"idx=,W=,dp= "<<idx<<" "<<W<<" "<<dp[idx]
}*/


struct memoFrame
{
    int index;
    int with;
    int without;
    int max_value;
    int capacity;
    int stage;
}stackMemo[N];

void memoBag(int index, int capacity, vector<int>& weights, vector<int>& values)
{
    int tt = 0;
    stackMemo[++tt] = { 0,0,0,0,capacity,0 };

    int max_value = 0;

    while (tt > 0)
    {
        //cout << "cnt=" << cnt << "\n";
        memoFrame& now = stackMemo[tt];
        //cout << "当前函数层为,index,capacity,stage=" << now.index << " " << now.capacity << " " << now.stage << "\n";
        if ((now.index == n || now.capacity <= 0)) {
            memoFrame& last = stackMemo[tt - 1];
            last.max_value = 0;
            //cout << "当前层为：，返回给上一层的返回值为" << now.index << " " << now.capacity << " " << last.max_value << "\n";
            tt--;
            //cout << "出栈：index,capacity,return" << now.index << " " << now.capacity << " " << last.max_value << "\n";
            continue;
        }
        if (dp[now.index][now.capacity] != -1)
        {
            memoFrame& last = stackMemo[tt - 1];
            last.max_value = dp[now.index][now.capacity];
            //cout << "当前层为：，返回给上一层的返回值为" << now.index << " " << now.capacity << " " << last.max_value << "\n";
            tt--;
            //cout << "出栈：index,capacity,return" << now.index << " " << now.capacity << " " << last.max_value << "\n";
            continue;
        }

        if (now.stage == 0)
        {
            stackMemo[++tt] = { now.index + 1,0,0,0,now.capacity,0 };
            //cout << "压栈0：" << now.index + 1 << " " << now.capacity << " " << "\n";
            now.stage++;
        }
        else if (now.stage == 1)
        {
            now.without = now.max_value;
            //cout << "更新without：index, without:" << now.index << " " << now.without << "\n";
            now.stage++;
        }
        else if (now.stage == 2)
        {
            if (now.capacity >= weights[now.index]) stackMemo[++tt] = { now.index + 1, 0, 0, 0, now.capacity - weights[now.index], 0 };
            // cout << "压栈1：" << now.index + 1 << " " << now.capacity << " " << "\n";
            now.stage++;
        }
        else if (now.stage == 3)
        {
            if (now.capacity >= weights[now.index])
            {
                now.with = now.max_value + values[now.index];
                //cout << "更新with, index,with:" << now.index << " " << now.with << "\n";
            }
            now.stage++;
        }
        else if (now.stage == 4)
        {
            memoFrame& last = stackMemo[tt - 1];
            dp[now.index][now.capacity] = max(now.with, now.without);

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < W; j++)
                {
                    cout << dp[i][j] << " ";
                }
                cout << "\n";
            }

            last.max_value = dp[now.index][now.capacity];
            Sleep(1000);
            //cout << "更新dp: index,dp:" << now.index << " " << last.max_value << "\n";
            tt--;
            //cout << "出栈：index,capacity,return" << now.index << " " << now.capacity << " " << last.max_value << "\n";
        }
    }

}


int main() {
    cin >> n >> W;; // 读取物品数量和背包容量

    weights.resize(n);
    values.resize(n);

    for (int i = 0; i < n; ++i) {
        cin >> weights[i] >> values[i];
    }

    memset(dp, -1, sizeof(dp));


    memoBag(0, W, weights, values);


    cout << "最大价值：" << dp[0][W] << endl;

    return 0;
}

/*
6 10
1 6
2 5
3 10
5 30
7 15
6 25
*/

在这里插入图片描述

把三个题整合到一块

#include <iostream>
#include <vector>
#include <cstring>
#include<iomanip>
#include <windows.h>

using namespace std;

const int N = 2e4 + 5;

typedef long long LL;

int n, W;//n可以是二分的数组长度，也可以是背包的物品个数，W是背包容量

int ansPos=-1;//二分搜索到的答案位置

int arr[N];

int dp[505][1005]; // 备忘录数组
vector<int> weights;
vector<int> values;

struct binaryFrame {
    int l, r;
    int level;//记录当前层数
    int step;//记录步数
}stackBinary[N];

struct backFrame
{
    int index;
    int current_weight;
    int current_value;
    int step;
    vector<int> chosenItems;
    int stage;
}stackBack[N];

struct memoFrame
{
    int index;
    int with;
    int without;
    int max_value;
    int capacity;
    int stage;
}stackMemo[N];

void binarySearch(int l, int r, int key)
{
    int nowLevel = 1, nowStep = 0, tt = 0, L = l, R = r;
    tt++;
    stackBinary[tt] = { l,r,nowLevel,nowStep };
    cout<<right<<setw(50) << "压栈：" << "当前执行函数纸带范围为：(" << L << " , " << R << " )" << " 层数为" << nowLevel << " 执行步数为" << nowStep << "\n";
    Sleep(200);
    while (L < R)
    {
        int mid = L + R >> 1;
        if (arr[mid] >= key)
        {
            R = mid;
            stackBinary[++tt] = { L,R,++nowLevel,++nowStep };
            cout<<right<<setw(50) << "压栈：" << "当前执行函数纸带范围为：(" << L << " , " << R << " )" << " 层数为" << nowLevel << " 执行步数为" << nowStep << "\n";
            Sleep(200);
        }
        else {
            L = mid + 1;
            stackBinary[++tt] = { L,R,++nowLevel,++nowStep };
            cout<<right<<setw(50) << "压栈：" << "当前执行函数纸带范围为：(" << L << " , " << R << " )" << " 层数为" << nowLevel << " 执行步数为" << nowStep << "\n";
            Sleep(200);
        }
    }
    if (arr[R] == key) {
        ansPos = R;
    }

    while (tt > 0)
    {
        cout<<right<<setw(50) << "出栈：" << "当前执行函数纸带范围为：(" << stackBinary[tt].l << " , " << stackBinary[tt].r << " )" << " 层数为" << stackBinary[tt].level << " 执行步数为" << stackBinary[tt].step << "\n";
        Sleep(200);
        tt--;
    }

}

void backBag(int n, int capacity, int& max_value, vector<int>& weights, vector<int>& values, vector<int>& chosenItems, vector<int>& best_set)
{
    int tt = 0, nowStep = 0;
    stackBack[++tt] = { 0,0,0,0,{},0 };
    cout<<right<<setw(50) << "压栈：初始化压栈，压入 0 0 0 0 {} 0" << "\n";
    Sleep(200);

    while (tt > 0)
    {
        backFrame now = stackBack[tt];
        
        cout << right << setw(50) << "当前执行函数层为：下标为：" << now.index << " 当前重量：" << now.current_weight << " 当前价值：" << now.current_value << " 当前步数：" << now.step << "\n";
        Sleep(200);
        if (stackBack[tt].index >= n) {
            if (stackBack[tt].current_value > max_value && stackBack[tt].current_weight <= capacity)
            {
                max_value = stackBack[tt].current_value;
                best_set = stackBack[tt].chosenItems;
            }

            tt--;
            cout<<right<<setw(50) << "出栈1：出栈下标：" << now.index << " 当前重量：" << now.current_weight << " 当前价值：" << now.current_value << " 当前步数：" << now.step << "\n";
            Sleep(200);
            continue;
        }



        if (now.stage == 0) {//栈顶为初始状态的话直接下一层函数压栈
            chosenItems.push_back(now.index);
            stackBack[++tt] = { now.index + 1,now.current_weight + weights[now.index],now.current_value + values[now.index],now.step + 1,chosenItems,0 };
            cout<<right<<setw(50) << "压栈1: 压栈下标：" << now.index + 1 << " 压栈重量：" << now.current_weight + weights[now.index] << " 压栈价值：" << now.current_value + values[now.index] << " 压栈步数：" << now.step + 1 << "\n";
            Sleep(200);

            stackBack[tt - 1].stage++;
        }
        else if (now.stage == 1) {
            chosenItems.pop_back();
            stackBack[++tt] = { now.index + 1,now.current_weight,now.current_value,now.step + 1,chosenItems,0 };
            cout<<right<<setw(50) << "压栈2: 压栈下标：" << now.index + 1 << " 压栈重量：" << now.current_weight << " " << now.current_value << " " << now.step + 1 << "\n";
            Sleep(200);
            stackBack[tt - 1].stage++;
        }
        else if (now.stage == 2) {
            tt--;
            cout<<right<<setw(50) << "出栈2：" << now.index << " 出栈重量：" << now.current_weight << " 出栈价值：" << now.current_value << " 出栈步数" << now.step << "\n";
            Sleep(200);
        }

    }

}


void memoBag(int index, int capacity, vector<int>& weights, vector<int>& values)
{
    int tt = 0;
    stackMemo[++tt] = { 0,0,0,0,capacity,0 };

    int max_value = 0;

    while (tt > 0)
    {
        memoFrame& now = stackMemo[tt];
        cout<<right<<setw(50) << "当前函数层为,当前执行下标：" << now.index << " 当前背包剩余容量：" << now.capacity << " 当前stage:" << now.stage << "\n";
        Sleep(200);
        if ((now.index == n || now.capacity <= 0)) {
            memoFrame& last = stackMemo[tt - 1];
            last.max_value = 0;
            //cout << "当前层为：，返回给上一层的返回值为" << now.index << " " << now.capacity << " " << last.max_value << "\n";
            tt--;
            cout<<right<<setw(50) << "出栈：出栈下标：" << now.index << " 出栈时剩余背包容量：" << now.capacity << " 出栈返回值：" << last.max_value << "\n";
            Sleep(200);
            continue;
        }
        if (dp[now.index][now.capacity] != -1)
        {
            memoFrame& last = stackMemo[tt - 1];
            last.max_value = dp[now.index][now.capacity];
            //cout << "当前层为：，返回给上一层的返回值为" << now.index << " " << now.capacity << " " << last.max_value << "\n";
            tt--;
            cout<<right<<setw(50) << "出栈：出栈下标：" << now.index << " 出栈时剩余背包容量：" << now.capacity << " 出栈时返回值：" << last.max_value << "\n";
            Sleep(200);
            continue;
        }

        if (now.stage == 0)
        {
            stackMemo[++tt] = { now.index + 1,0,0,0,now.capacity,0 };
            cout<<right<<setw(50) << "压栈0：压栈下标：" << now.index + 1 << " 压栈背包容量；" << now.capacity << " " << "\n";
            Sleep(200);
            now.stage++;
        }
        else if (now.stage == 1)
        {
            now.without = now.max_value;
            //cout << "更新without：index, without:" << now.index << " " << now.without << "\n";
            now.stage++;
        }
        else if (now.stage == 2)
        {
            if (now.capacity >= weights[now.index]) stackMemo[++tt] = { now.index + 1, 0, 0, 0, now.capacity - weights[now.index], 0 };
             cout<<right<<setw(50) << "压栈1：压栈下标：" << now.index + 1 << " 压栈背包容量：" << now.capacity-weights[now.index] << " " << "\n";
             Sleep(200);
            now.stage++;
        }
        else if (now.stage == 3)
        {
            if (now.capacity >= weights[now.index])
            {
                now.with = now.max_value + values[now.index];
                //cout << "更新with, index,with:" << now.index << " " << now.with << "\n";
            }
            now.stage++;
        }
        else if (now.stage == 4)
        {
            memoFrame& last = stackMemo[tt - 1];
            dp[now.index][now.capacity] = max(now.with, now.without);

            last.max_value = dp[now.index][now.capacity];
            //cout << "更新dp: index,dp:" << now.index << " " << last.max_value << "\n";
            tt--;
            cout<<right<<setw(50) << "出栈：出栈下标：" << now.index << " 出栈时背包容量：" << now.capacity << " 这一层出栈的返回值：" << last.max_value << "\n";
            Sleep(200);
        }
    }

}


int main() 
{
    int op;
    cout<<right<<setw(50) << "请选择要执行的递归函数模拟：1.二分搜索，2.回溯法，3.备忘录法\n";
    while(cin >> op) {
        if (op == 1) {
            int key;
            cout << right << setw(50) << "栈模拟递归二分算法\n\n\n";
            cout << right << setw(50) << "请输入查询数组长度\n";
            cin >> n;
            cout << right << setw(50) << "请输入" << n << "个数字\n";
            for (int i = 0; i < n; i++)
            {
                cin >> arr[i];
            }
            cout << right << setw(50) << "请输入需要查找的数字key\n";
            cin >> key;
            binarySearch(0, n - 1, key);
            if (ansPos == -1) cout << right << setw(50) << "找不到这个吊数\n";
            else cout << right << setw(50) << "数字" << key << "在数组中的第" << ansPos + 1 << "个位置\n";
        }
        else if (op == 2)
        {
            weights.clear();
            values.clear();

            cout << right << setw(50) << "栈模拟递归回溯算法\n\n\n";
            cout << right << setw(50) << "请输入物品件数和背包容量\n";
            cin >> n >> W;
            cout << right << setw(50) << "请输入" << n << "件物品的质量和价值\n";
            for (int i = 0; i < n; i++)
            {
                int x, y;
                cin >> x >> y;
                weights.push_back(x);
                values.push_back(y);
            }
            int max_value = -1;
            vector<int> best_set;
            vector<int> chosenItems;
            backBag(n, W, max_value, weights, values, chosenItems, best_set);
            cout << right << setw(50) << "可以获得的最大价值为:" << max_value << "\n";
            for (auto i : best_set)
            {
                cout << right << setw(50) << "选择了第" << i + 1 << "件物品\n";
            }
        }
        else if (op == 3)
        {
            weights.clear();
            values.clear();

            cout << right << setw(50) << "栈模拟递归备忘录算法\n\n\n";
            cout << right << setw(50) << "请输入物品件数和背包容量\n";
            cin >> n >> W;
            cout << right << setw(50) << "请输入" << n << "件物品的质量和价值\n";
            for (int i = 0; i < n; i++)
            {
                int x, y;
                cin >> x >> y;
                weights.push_back(x);
                values.push_back(y);
            }
            memset(dp, -1, sizeof(dp));


            memoBag(0, W, weights, values);
            cout << right << setw(50) << "能获得的最大价值为：" << dp[0][W] << "\n";
        }

        cout << right << setw(50) << "1.继续，2.结束\n";
        cin >> op;
        if (op == 2) break;
        cout << right << setw(50) << "请选择要执行的递归函数模拟：1.二分搜索，2.回溯法，3.备忘录法\n";

    }

    return 0;
}

/*二分搜索样例输入
10
1 2 3 4 5 6 7 8 9 10
2
*/

/*回溯与备忘录样例输入
6 10
1 6
2 5
3 10
5 30
7 15
6 25
*/

/*需要模拟的二分递归函数
int erfen(int arr[], int l, int r, int key)
{
    int ans = -1;


    int mid = l + r >> 1;

    if (arr[mid] == key && l == r) return r;

    if (l >= r) return -1;
    if (arr[mid] >= key) {
        ans = erfen(arr, l, mid, key);
    }
    else {
        ans = erfen(arr, mid + 1, r, key);
    }

    return ans;
}
*/

/*
// 需要模拟的递归回溯函数
void knapsack(int index, int current_weight, int current_value, int capacity, const vector<int>& weights, const vector<int>& values, vector<int>& chosen_items) {
    // 基础情况：如果考虑完所有物品
    if (index == weights.size()) {
        // 检查当前物品集合是否是一个有效解
        if (current_weight <= capacity && current_value > max_value) {
            max_value = current_value;
            best_set = chosen_items;
        }
        return;
    }

    // 选择当前物品
    chosen_items.push_back(index);
    knapsack(index + 1, current_weight + weights[index], current_value + values[index], capacity, weights, values, chosen_items);
    chosen_items.pop_back(); // 回溯

    // 不选择当前物品
    knapsack(index + 1, current_weight, current_value, capacity, weights, values, chosen_items);
}*/

/*需要模拟的备忘录递归函数
// 递归函数，包含备忘录算法逻辑，改为void类型
void knapsack(int idx, int W, int N, int& maxVal) {
    // 基本情况
    if (idx == N || W == 0) {
        maxVal = 0;
        cout << "边界：" << idx << " " << W << " " << maxVal << "\n";
        return;
    }
    // 检查是否已经计算过
    if (dp[idx][W] != -1) {
        maxVal = dp[idx][W];
        cout << "已经计算过：" << idx << " " << W << " " << maxVal << "\n";
        return;
    }
    // 选择不包含当前物品
    knapsack(idx + 1, W, N, maxVal);
    int without = maxVal; // 从上一次递归中获取结果
    cout << "without:" << idx << " " << W << " " << without << "\n";

    int with = 0;
    // 选择包含当前物品，如果背包容量足够
    if (W >= weight[idx]) {
        knapsack(idx + 1, W - weight[idx], N, with);
        with = values[idx] + with; // 添加当前物品的价值
        cout << "with:" << idx << " " << W << " " << with << "\n";
    }

    // 计算最大价值并存储备忘录结果
    maxVal = max(without, with);
    dp[idx][W] = maxVal; // 存储备忘录结果
    //cout<<"idx=,W=,dp= "<<idx<<" "<<W<<" "<<dp[idx]
}*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/753290.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

cartographer从入门到精通（一）：cartographer介绍

cartographer从入门到精通（一）：cartographer介绍

一、cartographer重要文档 有关cartographer的资料有2个比较重要的网站&#xff0c;我们的介绍也是基于这两个网站&#xff0c;其中会加入自己的一些理解&#xff0c;后续也有一些对代码的修改&#xff0c;来实现我们想完善的功能。 1-Cartographer 2-Cartographer ROS 第1个…
阅读更多...
如何使用飞书快捷指令无感记账，ios版

如何使用飞书快捷指令无感记账，ios版

总结 很多人无法长期坚持记账&#xff0c;主要是每次消费需要打开手机软件&#xff0c;一系列繁琐的操作&#xff0c;导致过程中可能就忘了。 今天给大家带来飞书自动记账。 演示视频 点击查看&#xff1a;https://www.douyin.com/video/7312857946382241063 安装 下载快捷…
阅读更多...
【java计算机毕设】网上商城系统java MySQL ssm vue html maven项目设计代码源码+文档PPT

【java计算机毕设】网上商城系统java MySQL ssm vue html maven项目设计代码源码+文档PPT

1项目功能 2项目介绍 系统功能&#xff1a; 网上商城系统包括管理员、用户俩种角色。 管理员功能包括个人中心模块用于修改个人信息和密码、管理员管理、基础数据管理、论坛管理、商品管理、浏览记录管理、公告信息管理、用户管理、轮播图信息。 用户功能包括个人中心模块用于…
阅读更多...
【Pyspark-驯化】spark中高效保存数据到hive表中：stored as PARQUET

【Pyspark-驯化】spark中高效保存数据到hive表中：stored as PARQUET

【Pyspark-驯化】spark中高效保存数据到hive表中&#xff1a;stored as PARQUET 本次修炼方法请往下查看 &#x1f308; 欢迎莅临我的个人主页 &#x1f448;这里是我工作、学习、实践 IT领域、真诚分享 踩坑集合&#xff0c;智慧小天地&#xff01; &#x1f387; 免费获取相关…
阅读更多...
python数据分析与可视化一

python数据分析与可视化一

公共部分 # 引入数据分析工具 Pandas import pandas as pd # 引入数据可视化工具 Matplotlib import matplotlib.pyplot as plt # 引入数据可视化工具 Seaborn (基于matplotlib) import seaborn as sns # 解决输出时的列名对齐问题 pd.set_option(display.unicode.east_…
阅读更多...
短视频利器 ffmpeg （2）

短视频利器 ffmpeg （2）

ffmpeg 官网这样写到 Converting video and audio has never been so easy. 如何轻松简单的使用&#xff1a; 1、下载 官网&#xff1a;http://www.ffmpeg.org 安装参考文档&#xff1a; https://blog.csdn.net/qq_36765018/article/details/139067654 2、安装 # 启用RPM …
阅读更多...
华强盛网络变压器外部电路如何接线

华强盛网络变压器外部电路如何接线

图一是 华强盛 Hqst 网络变压器工厂19926430038 华强盛电子导读&#xff1a; 网络变压器的外部电路接线通常依赖于其设计和用途。一般来说&#xff0c;网络变压器有多个端口&#xff0c;每个端口可能用于不同的连接或功能。以下是一些可能的接线方式&#xff1a; 1. **主电源…
阅读更多...
自研网关架构设计

自研网关架构设计

网关项目 1. 了解网关网关横向对比为什么自研网关 2. 架构设计技术栈技术要点异步化设计使用缓存缓冲合理使用串行化吞吐量为王合适的工作线程 架构图 1. 了解网关 概念 访问数据、业务逻辑或功能的 “前门”负责处理接受和处理调用过程中的所有任务 类型 RESTful APl 使用…
阅读更多...
核方法总结（三）———核主成分（kernel PCA）学习笔记

核方法总结（三）———核主成分（kernel PCA）学习笔记

一、核主成分 1.1 和PCA的区别 PCA &#xff08;主成分分析&#xff09;对应一个线性高斯模型&#xff08;参考书的第二章&#xff09;&#xff0c;其基本假设是数据由一个符合正态分布的隐变量通过一个线性映射得到&#xff0c;因此可很好描述符合高斯分布的数据。然而在很多实…
阅读更多...
深入分析 Android BroadcastReceiver (七)

深入分析 Android BroadcastReceiver (七)

文章目录 深入分析 Android BroadcastReceiver (七)1. 高级应用场景1.1 示例&#xff1a;动态权限请求1.2 示例&#xff1a;应用内通知更新 2. 安全性与性能优化2.1 示例&#xff1a;设置权限防止广播攻击2.2 示例&#xff1a;使用 LocalBroadcastManager2.3 示例&#xff1a;在…
阅读更多...
零成本打造精品宣传册

零成本打造精品宣传册

​随着互联网的发展&#xff0c;企业和个人对宣传册的需求日益增长&#xff0c;然而&#xff0c;高质量的宣传册制作往往需要不菲的成本。那么&#xff0c;如何零成本打造精品宣传册呢&#xff1f; 一、明确定位和目标群体 在制作宣传册之前&#xff0c;首先要明确其定位和目标…
阅读更多...
关于怎么将wireshark抓包视频流转为视频播放出来

关于怎么将wireshark抓包视频流转为视频播放出来

0.安装wireshark 安装PotPlayer 1.将以下两个插件放入 C:\Program Files\Wireshark\plugins 目录中 2.筛选视频流数据包&#xff0c;右键Decode As… 改为RTP 或者 右键->follow&#xff08;追踪流&#xff09;->UDP stream 然后叉掉弹窗 3.选择菜单Edit->Prefe…
阅读更多...
职责链让树状分支更严谨更易读更易维护

职责链让树状分支更严谨更易读更易维护

业务场景 传统方式就不列举了 职责链解决 Chain 类 class Chain {fn: Function;successor: any;constructor(fn: Function) {this.fn fn;this.successor null;}setNextSuccessor(successor: any) {return (this.successor successor);}passRequest() {var ret this.fn.a…
阅读更多...
微信公众号扫码授权登录

微信公众号扫码授权登录

【微信扫登录】原理说明 1、准备工作&#xff1a;注册开放微信公众号。获得此账号的AppID和AppSecret。 2、发起授权登录&#xff1a;通过授权链接或者扫码授权二维码的方式&#xff0c;获取登录code&#xff0c;通过code获取access_token。 3、成功获取access_token即代表登…
阅读更多...
[CTF]-PWN:mips反汇编工具，ida插件retdec的安装

[CTF]-PWN:mips反汇编工具，ida插件retdec的安装

IDA是没有办法直接按F5来反汇编mips的汇编的&#xff0c;而较为复杂的函数直接看汇编不太现实&#xff0c;所以只能借用插件来反汇编 先配置环境&#xff0c;下载python3.4以上的版本&#xff0c;并将其加入到环境变量中 下载retdec 地址&#xff1a;Release v1.0-ida80 ava…
阅读更多...
常见Web认证方式对比

常见Web认证方式对比

认证是一个在用户或者设备在访问一个受限的系统时&#xff0c;鉴定用户凭据的过程&#xff0c;即确认“你是谁”的问题。最常见的认证用户的方式是通过用户名和密码的形式进行校验&#xff0c;目前存在多种校验方式&#xff0c;本文将对其进行一个简单的对比&#xff0c;使得大…
阅读更多...
今天起，全球所有Mac用户可免费安装桌面版ChatGPT

今天起，全球所有Mac用户可免费安装桌面版ChatGPT

在 macOS 上&#xff0c;用户在安装新的 ChatGPT 应用程序后&#xff0c;使用 Option Space 的键盘组合即可快速调用 ChatGPT。 刚刚&#xff0c;OpenAI 宣布推出适用于 macOS 的应用程序。 虽然 Mac 应用程序尚未在 Mac App Store 中提供&#xff0c;但用户可以直接从 Open…
阅读更多...
Lean4Game 开发教程 | 数学形式化

Lean4Game 开发教程 | 数学形式化

引言 Lean 是一门用于形式化证明的编程语言&#xff0c;它允许严格证明数学定理和验证软件代码的正确性。 本篇介绍 Lean 游戏的编写和发布方式。这类游戏不仅利于对 Lean 本身的学习&#xff0c;对学科知识的理解&#xff0c;还能推动数学圈内人对 Lean 的接触学习。 Lean4…
阅读更多...
elementUI搭建使用过程

elementUI搭建使用过程

前言 Element&#xff0c;一套为开发者、设计师和产品经理准备的基于 Vue 2.0 的桌面端组 件库 安装 ElementUI 在终端命令行输入 npm i element-ui -S 在 main.js 中写入以下内容&#xff1a; import ElementUI from element-ui ; import element-ui/lib/theme-chalk/i…
阅读更多...
0-30 VDC 稳压电源，电流控制 0.002-3 A

0-30 VDC 稳压电源，电流控制 0.002-3 A

怎么运行的 首先&#xff0c;有一个次级绕组额定值为 24 V/3 A 的降压电源变压器&#xff0c;连接在电路输入点的引脚 1 和 2 上。&#xff08;电源输出的质量将直接影响与变压器的质量成正比&#xff09;。变压器次级绕组的交流电压经四个二极管D1-D4组成的电桥整流。桥输出端…
阅读更多...
最新文章

Copyright @ 2022~2023