算法课实验4

1.任务编排问题

任务编排问题取自算法导论上的一种解法，如果希望获得最多的任务数量的话，比方说有一个任务集合{S1}，首先我们可以在集合中查找任务结束最早的，然后我们获得了一个子问题，接下来在子问题中我们继续用同样的办法，找在子问题中结束时间最短的任务时间段，使用递归的方式，指导子问题已经小没有合适的任务时间段。

2.背包问题

场景：

话说有一哥们去森林里玩发现了一堆宝石，他数了数，一共有n个。但他身上能装宝石的就只有一个背包，背包的容量为C。这哥们把n个宝石排成一排并编上号： 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i] 。排好后这哥们开始思考：背包总共也就只能装下体积为C的东西，那我要装下哪些宝石才能让我获得最大的利益呢？

背包问题可以通过多个方式来最优解获得，我们定义一个函数式即为d(i,j),他的意思就是状态d(i, j)表示前i个宝石装到剩余体积为j的背包里能达到的最大的价值。d(i, j) = max(d(i-1, j), d(i-1, j-V[i-1]) + W[i-1])，这个算式还是很好理解的，之所以要写max是考虑到了第 i-1 个宝石装与不装的情况。那就直接看最核心的代码。

//这种有点类似穷举的方式
for(int i=0; i<=n; ++i){
    for(int j=0; j<=C; ++j){
        d[i][j] = i==0 ? 0 : d[i-1][j]; //前0个宝石装入背包就是没有东西可以装入所以要赋值为零,然后如果i不等于零的话，就是不装入的情况
        if(i>0 && j>=V[i-1])  d[i][j] >?= d[i-1][j-V[i-1]]+W[i-1];
    }
 }

C++实现

/**0-1 knapsack d(i, j)表示前i个物品装到剩余容量为j的背包中的最大重量**/
#include<cstdio>
using namespace std;
#define MAXN 1000
#define MAXC 100000

int V[MAXN], W[MAXN];
int d[MAXN][MAXC];

int main(){
    freopen("data.in", "r", stdin);//重定向输入流
    freopen("data.out", "w", stdout);//重定向输出流
    int n, C;
    while(scanf("%d %d", &n, &C) != EOF){
        for(int i=0; i<n; ++i)  scanf("%d %d", &V[i], &W[i]);
        
        for(int i=0; i<=n; ++i){
            for(int j=0; j<=C; ++j){
                d[i][j] = i==0 ? 0 : d[i-1][j];
                if(i>0 && j>=V[i-1])    d[i][j] >?= d[i-1][j-V[i-1]]+W[i-1];
            }
        }
        printf("%d\n", d[n][C]);//最终求解的最大价值
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

接下来我们需要对算法进行一些优化，对空间复杂度的一些优化。也就是在计算d(i, j)时我们用到了d(i-1,j)和d(i-1, j-V)的值。如果我们只用一个一维数组d(0)～d(C)来保存状态值可以么？将i方向的维数去掉，我们可以将原来二维数组表示为一维数据：d(i-1, j-V)变为d(j-V)， d(i-1, j)变为d(j)。当我们要计算d(i, j)时，只需要比较d(j)和d(j-V)+W的大小，用较大的数更新d(j)即可。等等，如果我要计算d(i, j+1)，而它恰巧需要用到d(i-1, j)的值，那么问题就出来了，因为你刚刚才把它更新为d(i, j)了，如果在二维数组中这个值并没有被替代。那么，怎么办呢？按照j递减的顺序即可避免这种问题。比如，你计算完d(i, j)，接下来要计算的是d(i,j-1)，而它的状态转移方程为d(i, j-1)=max{ d(i-1, j-1), d(i-1, j-1-V)+W }，它不会再用到d(i-1,j)的值！所以，即使该位置的值被更新了也无所谓。好，上代码：

memset(d, 0, sizeof(d));
for(int i=0; i<=n; ++i){
    if(i>0) scanf("%d %d", &V,&W);
    for(int j=C;j>=0; --j){
        if(j>=V && i>0) d[j] >?= d[j-V]+W;
    }
}

算法课实验4