0-1背包问题（递归解决）

 问题剖析：

   0-1背包问题规定每个物品要么选，要么不选。因此可以设置物品选择向量为y=[y1,y2,…yn], 那么当yn=1时，y'=[y1, y2, …yn-1],必然为f(n-1, C-wn)的物品选择向量，当yn=0时，必然为f(n-1,C)的最优物品选择向量。所以此时可以考虑动态规划解法。

    得到根据上面的分析，我们可以得到如下的递归式:

      当wn>C时， f(n,C)=f(n-1,C);

      当wn<=C时，f(n，C) = max(f(n-1,C), vn+f(n-1, C-wn) );

      初始条件为：f(i, 0) = 0; f(0,i) = 0; f(0,0) = 0;

  输入代码：

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int limitM;//限制的总重量
int option[100];
int n;//物品种数
struct Bag
{
    int weight;
    int value;
} num[100];
int find(int n, int M)
{
    if (n==0 || M==0)//当物品数量为0，或者背包容量为0时，最优解为0
    {
        return 0;
    }
    else
    {
        //从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
        for (int i=n-1; i>=0; i--)
        {
            //如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
            //在这种情况的最优解为f(n-1,C)

            if (num[i].weight>M)
            {
                option[i]=0;
                return find(n-1,M);
            }
            else
            {
                int temp1 = find(n-1,M);//不选择物品i的情况下的最优解
                int temp2 = num[i].value + find(n-1,M-num[i].weight);//选择物品i的情况下的最优解

                //返回选择物品i和不选择物品i中最优解大的一个
                if (temp1 > temp2)
                {
                    option[i]=0;//这种情况下表示物品i未被选取
                    return temp1;
                }
                else
                {
                    option[i]=1;//物品i被选取
                    return temp2;
                }
            }
        }
    }
}
int main()
{
    int k;
    char c;
    cout<<"物品种数：";
    cin>>n;
    for(k=0; k<n; k++)
    {
        cout<<"第"<<k+1<<"种物品(重量，价值):";
        cin>>num[k].weight>>c>>num[k].value;
    }
    cout<<"背包所能承受的总重量：";
    cin>>limitM;
    cout<<"最佳装填方案是："<<endl;
    for (int i=0; i<n; i++)
    {
        if (option[i]==1)//为1表示相应的物品被选取
        {
            cout << "第"<<i+1<<"种物品"<<endl;
        }
    }
    cout<<"总价值="<<find(n,limitM)<<endl;
    return 0;
}

运行截图：

总结：

练了几次，终于会用背包算法解决问题了！