实践是真理最好的老师，在手写代码入门C语言之后，是不是有一种算法不过尔尔的错觉？没错，就是错觉，算法是语言的灵魂，在简单的算法尝试过后，我们可以开始进阶一些比较厉害的代码了。

算法进阶篇第一个问题当然是最常用也是最典型的背包问题了，这不仅仅是一个包包这么简单，它的本质是通过编程实现放入背包物品价值的最大化，俗称线性最优解问题，迫不及待了吧，现在就看看这个问题是怎么样的。

设有一个背包可以放入的物品重量为V，现有n件物品，重量分别是 c1,c2,c3,…cn，价值分别为 w1,w2,w3,…wn。

问能否从这n件物品中选择若干件放入背包中，使得放入的物品的价值和最大？

此时我是懵逼的……

懵逼表情.jpg

[基本思路]：

01 背包问题 0 表示不放入，1 表示放入。

用子问题定义状态：即

f[i][v]表示前i件物品恰放入一个容量为v的背包可以获取得到的最大价值。

可以得到以下状态转移方程。

f[i][v] = max {f[i-1][v],f[i-1][v-c[i]] + w[i]} ;

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

思路我都懂，麻烦你直接告诉我怎么办吧！

懵逼循环.jpg

好的，接下来就是码代码了：

[cpp] view plain copy

include <stdio.h>

include <string.h>

define max(a,b) ((a>b)?a:b)

int main()
{
int i,j;
/**
* 最大重量 V = 20
* 物体总共个数 N = 5
/
int V = 20, N = 5;
/*
* 每个物体的重量
/
int Weight[6] = {0, 1, 3, 5, 7, 9};
/*
* 每个物体的价值
/
int Value[6] = {0, 10, 2, 5, 4, 3};
/*
* 辅助数组
*/

int f[6][21]; 
memset(f,0,sizeof(f));
for (i = 1; i <= N; i++)  
{  
    for (j = 1; j <= V; j++)  
    {  
        /** 
         * j-Weight[i] == 0 表示该物体的重量刚好等于最大允许重量 
         */  
        if (j-Weight[i] >= 0)  
        {  
            f[i][j] = max(f[i-1][j],f[i-1][j-Weight[i]] + Value[i]);  
        }  
        else  
        {  
            f[i][j] = f[i-1][j];  
        }  

        printf("%-5d",f[i][j]);  
    }  

    printf("\n");  
}  

printf("The final result = %d",f[5][20]);  

return 0;  

}

输出结果如下：

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
10 10 10 12 12 15 15 15 17 17 17 17 17 17 17 17 17 17 17 17
10 10 10 12 12 15 15 15 17 17 17 17 19 19 19 21 21 21 21 21
10 10 10 12 12 15 15 15 17 17 17 17 19 19 19 21 21 21 21 21
The final result = 21

Question:如何将2维数组 f转换成为1维数组？

f[i][v] = max {f[i-1][v],f[i-1][v-c[i]] + w[i]} ;

根据公式可以知道，f[i][v] 只和上一行[1,v] 之间的数相关，于是我们简化二维数组变成一维数组存储。而必须优先计算f[v]，因为从前到后操作会破快之前上一行保留下来的数据，造成错误。

好了，剩下的代码就让小伙伴们细细求索吧，当然啦，具体实现的代码肯定在下一次更新，但也可以加企鹅群：七一零，五二零，三八一，推荐人：柳猫，审核秒过，让我们一起来学C语言

程序媛.jpg