01背包问题（一个物品只能选一次）

解题思路:

注意事项:1.  动态规划问题，它的思想其实就是先保存所有情况，然后在所有情况中找到解，可以创建一个”备忘录“，把每一个情况写到这个备忘录中，直到所有的情况都写到备忘录的时候，找到我们满意的解答。

2.  疑问一：max(c[i-1][j],c[i-1][j-a[i]]+b[i])这个代码是什么意思？

3.  答：就是要看要不要装下这个物品，前者是不装入本物品，后者是要装本物品。能装入第i个物品的条件是要提前腾出正好够装它的位置。当然你既然装入了，那么价值就要加上他的价值b[i]。

4.  eg:c[i-1][j-a[i]]，这个假如i=4,j=7,a[i]=3，那么就是c[3][3]，c[3][3]的最好情况我们已经保存到备忘录了，直接用就行了。

参考代码:

#include<stdio.h>

    int max(int e,int f);//函数调用的声明

    int main()

    { //这里a数组用来保存我们的每一个东西的重量，b数组来保存价值大小

    int a[31],b[201],dp[31][201]={0}; //二维数组用来当作我们保存情况的”备忘录“。a：物品重量数组 b：物品价值数组

    //dp[i][j]表示前i个物品，此时背包容量为j所获的最大价值

    int n,w;//n:number物品的编号且有共有n个物品 w:weight背包的最大载荷

    int i,j;

    scanf("%d%d",&w,&n);//读入声明的最大载荷和物品数量

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

    {

    scanf("%d%d",&a[i],&b[i]); //按1~n的编号读入物品的重量和价值存入数组

    }

    for(i=1;i<=n;i++) //放物品一个一个放（遍历物品编号）

    {

    for(j=1;j<=w;j++) //背包容量依次增加（遍历物品重量）

    {

    if(a[i]>j) //这里是物品的重量大于我们的背包重量，即不装入背包

    {

    dp[i][j]=dp[i-1][j]; //第i个放不下，此时最大价值和上一个（i-1）个一样

    }

    else //如果放的下第i个物品，要考虑要不要装下。

    {//此时最大价值=试完第i-1个且留下第i个物品重量的最大价值+b[i](第i个物品的价值)

    dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]);//此时的最大价值为装了第i-1的价值和装第i个的价值二者的较大值

    }

    }

    }

    printf("%d",dp[n][w]);

    }

    int max(int e,int f) //自定义比较函数

    {

    int c;

    if(e>f)//以下是比较大小

    c=e;

    if(e<f)

    c=f;

    return c;

    }