算法导论第三版

当我刷到动态规划这一章的时候，突然想起以前的部门研发比武，就是一道需要运用动态规划思想来处理的题目，团灭了99%的人，而我也是这99%中的一员，哈哈，只怪出题的人太狠了。

以下的代码是汽车车间装配时间最短的代码习题，懒于整理，折叠起来：

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

struct move_time {
int i;
int j;
    move_time() : i(0), j(0) {}
    move_time(int x, int y) : i(x), j(y) {}
};

void print_stations(const vector<int>& l, int lx, int n) {
int i = lx;
    cout << "line " << i << ", station " << n << endl;
for (int j=n-1; j>0; j--) {
        i = l[j];
        cout << "line " << i << ", station " << j << endl;
    }
}

int main(int argc, char* argv[]) {
int s1[] = {7,9,3,4,8,4};
int s2[] = {8,5,6,4,5,7};
int len = 6;

    vector<int> vf1_a(s1, s1+len), vf2_a(s2, s2+len);
    vector<int> line(len, 0);
    vector<int> f1(len, 0), f2(len, 0);

int a_i[] = {2,3,1,3,4};
int a_j[] = {2,1,2,2,1};

    vector< struct move_time > pt(5,  move_time(0,0));

for (int n=0; n<pt.size(); n++) {
        pt[n].i = a_i[n];
        pt[n].j = a_j[n];
    }

int e1 = 2;
int e2 = 4;
int x1 = 3;
int x2 = 2;

int fx = 0;
int lx = 0;


    f1[0] = e1 + vf1_a[0];
    f2[0] = e2 + vf2_a[0];

int l=1;
for (; l<len; ++l) {
if (f1[l-1]+vf1_a[l] <= f2[l-1]+pt[l-1].j+vf1_a[l]) {
            f1[l] = f1[l-1]+vf1_a[l];
            line[l] = 1;
        } else {
            f1[l] = f2[l-1]+pt[l-1].j+vf1_a[l];
            line[l] = 2;
        }

if (f2[l-1]+vf2_a[l] <= f1[l-1]+pt[l-1].i+vf2_a[l]) {
            f2[l] = f2[l-1]+vf2_a[l];
            line[l] = 2;
        } else {
            f2[l] = f1[l-1]+pt[l-1].i+vf2_a[l];
            line[l] = 1;
        }
    }

    l = len-1;
if (f1[l]+x1 <= f2[l]+x2) {
        fx = f1[l]+x1;
        lx = 1;
    } else {
        fx = f2[l]+x2;
        lx = 2;
    }

    print_stations(line, lx, len);

    return 0;
}

 

贪心算法属于动态规划的延伸。

动态规划是自底而上的，贪心算法是自顶而下的。

贪心算法能解决很多求最优解的问题。主要在于如何做出贪心选择和确定最优子结构，这个就根据具体的问题来分析了，开始有点玄学的味道了。