0-1背包问题总结【递归算法与二进制算法】

听学长讲了算法之后，总结了一下背包问题的两种方法，当然这并不是最优的，会tle。

题目描述

给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。
 

输入

输入包含多组测试用例。

第一个数据是背包的容量为c（1≤c≤2500），第二个数据是物品的数量为n。接下来n行是物品i的重量是wi，其价值为vi。所有的数据全部为整数，且保证输入数据中物品的总重量大于背包的容量。
当c＝0时，表示输入数据结束。
 

输出

对每组测试数据，输出装入背包中物品的最大价值。

第一种方法，递归算法：考虑每一种情况拿还是不拿，也可对齐进行可行性剪枝，如果当前的重量已经超过总重，直接return；

1. 
   #include <stdio.h>
   #include <stdlib.h>
   #include <math.h>
   int ans=0;
   int z;
   void beibao(int sumw,int sumv,int n,int step,int v[],int w[],int c){
           if(step==n+1)
           {
               if(sumw<=c)
                   ans=fmax(ans,sumv);
               return;
           }
       //拿
           beibao(sumw+w[step],sumv+v[step],n,step+1,v,w,c);
       //不拿
           beibao(sumw,sumv,n,step+1,v,w,c);
   }
   int main()
   {
       int n,c;
       int v[100];
       int w[100];
       scanf("%d",&n);
       scanf("%d",&c);
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&w[i]);
           scanf("%d",&v[i]);
       }
       beibao(0,0,n,1,v,w,c);
       printf("%d\n",ans);
   
       return 0;
   }

 第二种方法，二进制转化法，其实道理是一样的，每一件都对应一个状态，不拿为0，拿为1，如果n=3，则情况为从000到111共8种，所以代码如下：

#include <stdio.h>
#include <math.h>
int main(){
    int w[2000];
    int v[2000];
    int a[100];
    int n,c;
    int cnt;
    int m;
    int sum1=0,sum2=0,ans=-1;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&n,&c);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            scanf("%d",&v[i]);
        }
        for(int i=0;i<pow(2,n);i++)
        {
        sum1=sum2=0;
            cnt=0;
            int z=i;
            while(z)
            {
                a[++cnt]=z%2;
                z/=2;
            }
            for(int k=1;k<=n;k++)
            {
                sum1+=a[k]*w[k];
                sum2+=a[k]*v[k];
            }
        if(sum1>c)
            continue;
        else
            ans=fmax(ans,sum2);
        }
        printf("%d\n",ans);
    }
    return 0;
}

但是要注意这两种算法，只适用于n很小的时候，如果n>10,会tle，优化的算法还有学会见谅了。

菜鸟代码，大神勿喷。