柿子饼同学 发表于 2022-3-18 22:47:39

动态规划求最大值

图片在下 , 就是灰色占据的是时间 , 红色代表这段时间能赚到的钱 , 一段时间只能做一件事
假设一件事做完中间可以不停顿接着做另一件事 , 问能赚到的钱最大值是多少
我的代码:#include <bits/stdc++.h>
using namespace std;

int v = {-1, 5, 1, 8, 4, 6, 3, 2, 4};
int ni = {-1, 0, 0, 0, 1, 0, 2, 3, 5};
int opt(int);
int opt(int n){
        int max;
        if(n == 1 || n == 2){
                return 5;
        }
        else{
                if(v + opt(ni) > opt(n-1)){
                        max += v + opt(ni);
                }
                else{
                        max += opt(n-1);
                }
        }
        return max;
}
int main(){
        int a = opt(8);
        printf("%d", a);
        return 0;
}
它又不输出了 , 不知道怎么回事
求指教

傻眼貓咪 发表于 2022-3-18 23:32:55

本帖最后由 傻眼貓咪 于 2022-3-19 08:09 编辑

答案是 13 吗？#include <iostream>
#include <vector>

// 开始时间、结束时间
typedef struct {
        unsigned start, end;
}Time;

// 工作时间、收入
typedef struct {
        Time time;
        unsigned income;
}Timer;

// 计算收入
unsigned income(std::vector<Timer> V, Time T, unsigned sum = 0) {
        std::vector<unsigned> temp;
        unsigned max = 0;
        for (const Timer &t : V) {
                // 寻找下一个吻合的时间点路线
                if (t.time.start >= T.end) {
                        temp.push_back(income(V, t.time, t.income));
                }
        }
        for (unsigned u : temp) if (u > max) max = u;
        return sum + max;
}

int main() {
        unsigned arr[] = { { 1, 4, 5 }, { 3, 5, 1 }, { 0, 6, 8 }, { 4, 7, 4 }, { 3, 8, 6 }, { 5, 9, 3 }, { 6, 10, 2 }, { 8, 11, 4 } };
        std::vector<Timer> V;
        for (int i = 0; i < 8; i++) V.push_back({ { arr, arr }, arr });
        unsigned max = 0;
        for (const Timer &t: V) {
                if (income(V, t.time, t.income) > max) {
                        max = income(V, t.time, t.income);
                }
        }
        std::cout << max;
        return 0;
}13

柿子饼同学 发表于 2022-3-19 22:39:22

傻眼貓咪 发表于 2022-3-18 23:32
答案是 13 吗？

求问for (const Timer &t : V) {
这句什么意思,是不是给Timer 起个名字叫 t 还有这句for (int u : temp) if (u > max) max = u;

柿子饼同学 发表于 2022-3-19 22:49:46

傻眼貓咪 发表于 2022-3-18 23:32
答案是 13 吗？

int income(vector<Timer> V, Time T, int sum = 0){
        vector<int> temp; // ???
        int max = 0; //最大值
        for(const Timer &t : V){ // ???
                if(t.time.start >= T.end){ //为什么t.time.start换成T.start就不对了
                        temp.push_back(income(V, t.time, t.income));
                }
        }
        for(int u : temp) if (u > max) max = u;
        return sum + max;
}
这个函数它是怎么实现功能的能详细讲讲嘛 , 谢谢{:10_266:}

柿子饼同学 发表于 2022-3-19 22:50:42

傻眼貓咪 发表于 2022-3-18 23:32
答案是 13 吗？

答案对的{:10_254:}

傻眼貓咪 发表于 2022-3-19 23:01:28

柿子饼同学 发表于 2022-3-19 22:39
求问
这句什么意思,是不是给Timer 起个名字叫 t 还有这句

for (const Timer &t : V) {} 这段代码是为了避免深拷贝，而引用原值，const 为了不让改变其值。当然你也可以直接 for(Timer t: V) 也行。

例子：
for (auto x: V) 如果只是要读取向量数组中的元素值，将循环变量定义为拷贝类型
for (auto &x: V) 如果要更改向量数组中的元素值，必须将循环变量定义为引用类型
for (const auto x: V) 不想更改值，只想引用，不想拷贝（避免深拷贝）

for (int u : temp) if (u > max) max = u; 这段代码是递归后结果，储存进 temp 里（意思就是分叉路线的最后结果，找出最大值），考虑到路线可能不止一条。

傻眼貓咪 发表于 2022-3-19 23:09:59

柿子饼同学 发表于 2022-3-19 22:39
求问
这句什么意思,是不是给Timer 起个名字叫 t 还有这句

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> B = {1, 2, 3, 4, 5};
    std::vector<int> C = {1, 2, 3, 4, 5};
   
    for(int x: A) x *= x; // <-------- 注意这里
    for(int &x: B) x *= x; // <-------- 注意这里
    // for(const int &x: C) x *= x;// <-------- 注意这里，如果这样写，会报错：error: assignment of read-only reference ‘x’，只能读，不能改写
   
    /*-------- 打印 --------*/
    for(int x: A) std::cout << x << " ";
    std::cout << std::endl;
   
    for(int x: B) std::cout << x << " ";
    std::cout << std::endl;

    for(int x: C) std::cout << x << " ";
    std::cout << std::endl;
   
    return 0;
}1 2 3 4 5
1 4 9 16 25
1 2 3 4 5

傻眼貓咪 发表于 2022-3-19 23:15:24

本帖最后由 傻眼貓咪 于 2022-3-19 23:17 编辑

柿子饼同学 发表于 2022-3-19 22:49
这个函数它是怎么实现功能的能详细讲讲嘛 , 谢谢

哈哈哈，抱歉了兄弟，因为我为了包装好看，所以写了 2 个结构体，一个是 Time，另一个是 Timer，至於 Timer 里的属性有 Time time，如我的代码：

// 开始时间、结束时间
typedef struct {
      unsigned start, end;
}Time;

// 工作时间、收入
typedef struct {
      Time time; // <---------------注意这里
      unsigned income;
}Timer;

而 t 是 Timer 结构体，其属性 t.time 又有属性 start 和 end

柿子饼同学 发表于 2022-3-20 20:57:35

傻眼貓咪 发表于 2022-3-19 23:15
哈哈哈，抱歉了兄弟，因为我为了包装好看，所以写了 2 个结构体，一个是 Time，另一个是 Timer，至於 T ...

结构体这种写法我知道 , 但是不懂函数怎么具体执行下来的{:10_266:}

傻眼貓咪 发表于 2022-3-20 21:26:56

柿子饼同学 发表于 2022-3-20 20:57
结构体这种写法我知道 , 但是不懂函数怎么具体执行下来的

慢慢来吧，大家一起学习学习吧{:10_254:}{:10_254:}{:10_254:}

柿子饼同学 发表于 2022-3-20 21:28:46

傻眼貓咪 发表于 2022-3-19 23:09


那这些跟for(int i = 0; i < 5; i++){
        A *= A;
}
有啥区别呢

柿子饼同学 发表于 2022-3-20 21:39:20

傻眼貓咪 发表于 2022-3-19 23:09


欸话说这是不是就是python里面 for iin A: i*= i 的意思呀

傻眼貓咪 发表于 2022-3-20 21:45:16

本帖最后由 傻眼貓咪 于 2022-3-20 21:47 编辑

柿子饼同学 发表于 2022-3-20 21:39
欸话说这是不是就是python里面 for iin A: i*= i 的意思呀
for(int x: A) x *= x;就好象 Python 里的 for i in A: i *= i 一样，只是拷贝值，不会影响原本的值

for(int &x: A) x *= x;就好象 for(int i = 0; i < 5; i++) A *= A; 一样，引用，并且会影响原本的值

柿子饼同学 发表于 2022-3-20 22:08:57

傻眼貓咪 发表于 2022-3-20 21:45
就好象 Python 里的 只是拷贝值，不会影响原本的值

就好象一样，引用，并且会影响原本的值

哇 , 还能这么写 , 长知识了

傻眼貓咪 发表于 2022-3-20 22:12:47

柿子饼同学 发表于 2022-3-20 22:08
哇 , 还能这么写 , 长知识了

{:10_298:}

傻眼貓咪 发表于 2022-3-20 22:15:54

柿子饼同学 发表于 2022-3-20 22:08
哇 , 还能这么写 , 长知识了

如果你想了解更多关于这点，可以往 C++ 的左值引用 & 和右值引用 && 研究研究。当然这里是非常深入的知识。我平常只会用皮毛而已，哈哈。{:10_264:}
页: [1]
查看完整版本: 动态规划求最大值