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

柿子饼同学

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int v[9] = {-1, 5, 1, 8, 4, 6, 3, 2, 4};
   
5. int ni[9] = {-1, 0, 0, 0, 1, 0, 2, 3, 5};
   
6. int opt(int);
   
7. int opt(int n){
   
8.         int max;
   
9.         if(n == 1 || n == 2){
   
10.                 return 5;
    
11.         }
    
12.         else{
    
13.                 if(v[n] + opt(ni[n]) > opt(n-1)){
    
14.                         max += v[n] + opt(ni[n]);
    
15.                 }
    
16.                 else{
    
17.                         max += opt(n-1);
    
18.                 }
    
19.         }
    
20.         return max;
    
21. }
    
22. int main(){
    
23.         int a = opt(8);
    
24.         printf("%d", a);
    
25.         return 0;
    
26. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-3-20 21:45:16

柿子饼同学 发表于 2022-3-20 21:39
欸话说这是不是就是python里面 for i  in A: i*= i 的意思呀

1. for(int x: A) x *= x;

复制代码

就好象 Python 里的

1. for i in A: i *= i 一样，

复制代码

只是拷贝值，不会影响原本的值

---

---

1. for(int &x: A) x *= x;

复制代码

就好象

1. for(int i = 0; i < 5; i++) A[i] *= A[i];

复制代码

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

跳转到最佳答案楼层

傻眼貓咪

答案是 13 吗？

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. // 开始时间、结束时间
   
5. typedef struct {
   
6.         unsigned start, end;
   
7. }Time;
   
8. 
   
9. // 工作时间、收入
   
10. typedef struct {
    
11.         Time time;
    
12.         unsigned income;
    
13. }Timer;
    
14. 
    
15. // 计算收入
    
16. unsigned income(std::vector<Timer> V, Time T, unsigned sum = 0) {
    
17.         std::vector<unsigned> temp;
    
18.         unsigned max = 0;
    
19.         for (const Timer &t : V) {
    
20.                 // 寻找下一个吻合的时间点路线
    
21.                 if (t.time.start >= T.end) {
    
22.                         temp.push_back(income(V, t.time, t.income));
    
23.                 }
    
24.         }
    
25.         for (unsigned u : temp) if (u > max) max = u;
    
26.         return sum + max;
    
27. }
    
28. 
    
29. int main() {
    
30.         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 } };
    
31.         std::vector<Timer> V;
    
32.         for (int i = 0; i < 8; i++) V.push_back({ { arr[i][0], arr[i][1] }, arr[i][2] });
    
33.         unsigned max = 0;
    
34.         for (const Timer &t: V) {
    
35.                 if (income(V, t.time, t.income) > max) {
    
36.                         max = income(V, t.time, t.income);
    
37.                 }
    
38.         }
    
39.         std::cout << max;
    
40.         return 0;
    
41. }

复制代码

1. 13

复制代码

柿子饼同学

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

求问

1. for (const Timer &t : V) {

复制代码

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

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

复制代码

柿子饼同学

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

1. int income(vector<Timer> V, Time T, int sum = 0){
   
2.         vector<int> temp; // ???
   
3.         int max = 0; //最大值
   
4.         for(const Timer &t : V){ // ???
   
5.                 if(t.time.start >= T.end){ //为什么t.time.start换成T.start就不对了
   
6.                         temp.push_back(income(V, t.time, t.income));
   
7.                 }
   
8.         }
   
9.         for(int u : temp) if (u > max) max = u;
   
10.         return sum + max;
    
11. }

复制代码

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

柿子饼同学

傻眼貓咪 发表于 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 还有这句

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. int main()
   
5. {
   
6.     std::vector<int> A = {1, 2, 3, 4, 5};
   
7.     std::vector<int> B = {1, 2, 3, 4, 5};
   
8.     std::vector<int> C = {1, 2, 3, 4, 5};
   
9.    
   
10.     for(int x: A) x *= x; // <-------- 注意这里
    
11.     for(int &x: B) x *= x; // <-------- 注意这里
    
12.     // for(const int &x: C) x *= x;  // <-------- 注意这里，如果这样写，会报错：error: assignment of read-only reference ‘x’，只能读，不能改写
    
13.    
    
14.     /*-------- 打印 --------*/
    
15.     for(int x: A) std::cout << x << " ";
    
16.     std::cout << std::endl;
    
17.    
    
18.     for(int x: B) std::cout << x << " ";
    
19.     std::cout << std::endl;
    
20. 
    
21.     for(int x: C) std::cout << x << " ";
    
22.     std::cout << std::endl;
    
23.    
    
24.     return 0;
    
25. }

复制代码

1. 1 2 3 4 5
   
2. 1 4 9 16 25
   
3. 1 2 3 4 5

复制代码

傻眼貓咪

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

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

1. // 开始时间、结束时间
   
2. typedef struct {
   
3.         unsigned start, end;
   
4. }Time;
   
5. 
   
6. // 工作时间、收入
   
7. typedef struct {
   
8.         Time time; // <---------------注意这里
   
9.         unsigned income;
   
10. }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

那这些跟

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

复制代码

有啥区别呢

柿子饼同学

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

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

傻眼貓咪

柿子饼同学 发表于 2022-3-20 21:39
欸话说这是不是就是python里面 for i  in A: i*= i 的意思呀

1. for(int x: A) x *= x;

复制代码

就好象 Python 里的

1. for i in A: i *= i 一样，

复制代码

只是拷贝值，不会影响原本的值

---

---

1. for(int &x: A) x *= x;

复制代码

就好象

1. 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++ 的左值引用 & 和右值引用 && 研究研究。当然这里是非常深入的知识。我平常只会用皮毛而已，哈哈。