01背包模板总结

　　前两天学习了一下动态规划中的一种背包问题，发现网上绝大多数模板都叙述的含糊不清，
关键部分看不懂让人感觉很难受，今天我就详细叙述一下01背包。
　　首先的问题当然是什么叫做01背包。
　　01背包:先举个01背包的题
　　　　有编号分别为a,b,c,d,e的五件物品，它们的重量分别是1,2,5,6,7，它们的
　　价值分别是1,6,18,22,28，每件物品数量只有一个，现在给你个承重为11的背包，如何
　　让背包里装入的物品具有最大的价值总和？
　　　　怎么个意思，就是物品只有一个，不能重复放，将哪些物品装入背包可使这些
　　物品的重量总和不超过背包容量，且价值总和最大，这就是01背包问题。

一,模板
以上面的01背包的问题为例子

#include<stdio.h>
int max[500][500];

int main(void)
{
    int w=11;                                         //背包容量
    int n=5;                                          //物品数量
    int value[5]={1,6,18,22,28};                      //相互对应的重量与价值
    int weight[5]={1,2,5,6,7};                        


    for(int i=0;i<=w;i ++)                             //M[n,W]
        max[0][i]=0;                                   max为最大价值数组，数组一维


    for(int j=1;j<=n;j++)                            //外层遍历放到第几个物品                                                             
    {                                                //想要求背包上限为11时的最大价值就要知道背包
        for(int k=1;k<=w;k++)                        //上限为1--10时的最大价值，内层遍历背包容量           
        {
            if(weight[j-1]>k)
            {                                        //第j个物品对应重量的下标减1，从0开始。
                max[j][k]=max[j-1][k];               //当加入的一个物品重量大于k，这个物品一定不能选
            }
            else
            {
                int a=max[j-1][k];                          //不选第j个物品, 也就是遍历之前的一个物品时的     
                                                            //最大价值           
                int b=value[j-1]+max[j-1][k-weight[j-1]];   //可以选第j个物品，选择这个物品
                /*
                    选第j个物品时，背包剩余容量为[k-weight[j-1]],所以你需要知道当物品遍历到[j-1]时,
                    此时的最大价值，用当前物品价值加上max[j-1][k-weight[j-1]]对应的最大价值
                */
                max[j][k]=a>b ? a:b;//选择第j个和不选第j个物品，那个大，返回哪个；
            }
                /*
                特别注意j,k代表着当背包容量为k时,往进放到第j个物品的最大价值，并且最重要保证遍历到第5个物品时，
                价值一定是最大的。
                */                                                                                                            
        }
    }
    printf("%d\n",max[n][w]);            //最终结果一定是当背包容量为w时，遍历到第n个物品时的最大价值
}