c语言背包算法（c语言背包问题）

大家好，我是小典，我来为大家解答以上问题。c语言背包算法，c语言背包问题很多人还不知道，现在让我们一起来看看吧！

1、#include<stdio.h>

2、int max(int a,int b)

3、{

4、 if (a>b) return a;

5、 else return b;

6、}

7、int main()

8、{

9、 //int max(int , int );

10、 int n,m,i,j;

11、 int data[101][2];

12、 int f[101][101];

13、 scanf("%d%d",&n,&m); //n表示个数，m表示能背的最大重量

14、 for(i=1;i<=n;i++)

15、 {

16、 scanf("%d%d",&data[i][0],&data[i][1]);

17、 } //我是数组从第一个开始记得，看着容易理解，没必要去省那么几B的内存

18、 for(i=0;i<=m;i++) f[0][i]=0;

19、 for(i=0;i<=n;i++) f[i][0]=0;

20、 for(i=1;i<=n;i++)

21、 for(j=1;j<=m;j++)

22、 {

23、 f[i][j]=0;

24、 if (j>=data[i][0])

25、 {

26、 f[i][j]=max(f[i-1][j],f[i-1][j-data[i][0]]+data[i][1]);

27、 //对于这件物品要么不选要么选，不选是f[i-1][j];

28、 //选的话为f[i-1][j-data[i][0]]此处j-data[i][0]是因为要选上一次就得少背j-data[i][0]的重量

29、 //才能装下这次的物品

30、 }

31、 else f[i][j]=f[i-1][j];

32、 }

33、 printf("%d ",f[n][m]);

34、 return 0;

35、}

36、然后常见的背包问题还有多重背包问题，对于每一个物品可能有多个这种可以预处理成一般的背包问题，就是把几个摊开，很简单就不解释了，当然也可以加一维.

37、还有就是完全背包问题他的状态转移方程是f[i,j]=max(f[i-1][j],f[i][j-data[i].v]);

38、他和01的区别只是要选的时候不是f[i-1][j-data[i].v]而是f[i][j-data[i].v]，这样就能选到自己了，如果是初学可能不好理解，慢慢理会吧，其实这个很妙，我当初用了很多种方法，都是错的，看了一时也没明白，后来豁然开朗，然后对动规的理解都上了一个层次.

39、还有就是多为背包，这个只需要加一维，理解了前面的自然就能做出来了，根本不需要再看状态转移方程了（事实上理解后01就能够做出来了）.

40、一句话：要多思考，反复思考

41、我很久没碰算法了，我没现成的代码这是我手打出来的，求分

本文到此讲解完毕了，希望对大家有帮助。