[已解决]动态规划求最大值

柿子饼同学

图片在下 , 就是灰色占据的是时间 , 红色代表这段时间能赚到的钱 , 一段时间只能做一件事
假设一件事做完中间可以不停顿接着做另一件事 , 问能赚到的钱最大值是多少
我的代码:

#include <bits/stdc++.h>
using namespace std;

int v[9] = {-1, 5, 1, 8, 4, 6, 3, 2, 4};
int ni[9] = {-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[n] + opt(ni[n]) > opt(n-1)){
                        max += v[n] + opt(ni[n]);
                }
                else{
                        max += opt(n-1);
                }
        }
        return max;
}
int main(){
        int a = opt(8);
        printf("%d", a);
        return 0;
}

它又不输出了 , 不知道怎么回事
求指教

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-3-20 21:45:16

柿子饼同学 发表于 2022-3-20 21:39
欸话说这是不是就是python里面 for i  in 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[i] *= A[i];

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

跳转到最佳答案楼层

傻眼貓咪

答案是 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[][3] = { { 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[i][0], arr[i][1] }, arr[i][2] });
        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-18 23:32
答案是 13 吗？

求问

for (const Timer &t : V) {

这句什么意思,是不是给Timer 起个名字叫 t 还有这句

for (int u : temp) if (u > max) max = u;

柿子饼同学

傻眼貓咪 发表于 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;
} 

这个函数它是怎么实现功能的能详细讲讲嘛 , 谢谢

柿子饼同学

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

答案对的

傻眼貓咪

柿子饼同学 发表于 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 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 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-19 23:15
哈哈哈，抱歉了兄弟，因为我为了包装好看，所以写了 2 个结构体，一个是 Time，另一个是 Timer，至於 T ...

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

傻眼貓咪

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

慢慢来吧，大家一起学习学习吧

柿子饼同学

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

那这些跟

for(int i = 0; i < 5; i++){
        A[i] *= A[i];
}

有啥区别呢

柿子饼同学

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

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

傻眼貓咪

柿子饼同学 发表于 2022-3-20 21:39
欸话说这是不是就是python里面 for i  in 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[i] *= A[i];

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

柿子饼同学

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

---

---

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

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

傻眼貓咪

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

傻眼貓咪

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

如果你想了解更多关于这点，可以往 C++ 的左值引用 & 和右值引用 && 研究研究。当然这里是非常深入的知识。我平常只会用皮毛而已，哈哈。