听学长讲了算法之后，总结了一下背包问题的两种方法，当然这并不是最优的，会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，优化的算法还有学会见谅了。

菜鸟代码，大神勿喷。