0/1 背包问题

/**
    ##########################  0/1 背包问题  #######################################


    <=动态规划方程===========================================================>

        f[i][V] 表示当背包总共容量为V的情况下，放i件物品所能获得的最大价值

        f[i][V] = max { f[i-1][V], f[i-1][V-w[i]]+p[i] }

    <=========================================================================>

    <=算法设计================================================================>

        递归算法：

        f(i,V)
        {
            if i equals 0 then do:
                return 0;
            if V < w[i] then do:
                return f(i-1,V);
            else do:
                return max(f(i-1,V),f(i-1,V-w[i]+p[i]));
        }

        递推算法：

        knapsack(int n,int V,int f[][],int p[],int w[])
        {
            for V = 1 to n do:
                f[0][V] = 0;
            for i = 1 to n do:
            {
                for j = 1 to V do:
                {
                    if(V<w[j])
                        f[i][V] = f[i-1][V];
                    else
                        f[i][V] = max(f(i-1,V),f(i-1,V-w[i]+p[i]));
                }
            }
            traceback();
            to get the answer;
        }
    <=========================================================================>
*/

//=======> C语言源代码实现 <========

#include<cstdio>
#define MAXN 20

//物品1,2...5的价值
int p[] = {0,6,3,5,4,6};
//物品1,2...5的体积
int w[] = {0,2,2,6,5,4};

//递归算法： 表示当背包总共容量为V的情况下，放i件物品所能获得的最大价值
int f(int i,int V);

//递推算法：
void knapsack(int n,int V,int ft[][MAXN],int p[],int w[]);
//回溯求最优解向量
void traceback(int x[],int n,int ft[][MAXN],int V);

//计算最大值
int max(int a,int b);

//程序执行入口
int main()
{
    printf("Using a recursive algorithm:\n");
    int maxValue = f(5,10);
    printf("when the count of goods is %d and the total volume of the bag is %d,\nthe maxValue is %d\n\n",5,10,maxValue);


    printf("Using a recursion algorithm:\n");
    int ft[MAXN][MAXN];
    knapsack(5,10,ft,p,w);
    printf("when the count of goods is %d and the total volume of the bag is %d,\nthe maxValue is %d\n",5,10,ft[5][10]);
    int x[MAXN];
    traceback(x,5,ft,10);
    printf("the best answer is (");
    for(int i=1;i<=5;i++)
        printf("%d,",x[i]);
    printf(")\n");

     return 0;
}

int max(int a,int b){
    return a>b?a:b;
}

//递归实现 p[] = {0,6,3,5,4,6}; w[] = {0,2,2,6,5,4}; 注意p,w中0只是拿来填充index = 0的时候没什么意义
int f(int i,int V)
{
    //当背包里面物品为0个的时候，价值当然为0
    if(i==0)
        return 0;

    //当所放物品的体积超过背包所提供最大体积
    //当然不能考虑把这个物品放入背包的情况
    if (V < w[i])
        return f(i-1,V);

    //当情况不是上面那样的时候
    //就要考虑把当前 i 物品放入背包
    else
        return max(f(i-1,V),f(i-1,V-w[i])+p[i]);
}

//递推算法 p[] = {0,6,3,5,4,6}; w[] = {0,2,2,6,5,4}; 注意p,w中0只是拿来填充index = 0的时候没什么意义
void knapsack(int n,int V,int ft[][MAXN],int p[],int w[])
{
    //初始化
    for(int i=0;i<=V;i++){
        ft[0][i] = 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=V;j++)
        {
            if(j<w[i])
                ft[i][j] = ft[i-1][j];
            else
                ft[i][j] = max(ft[i-1][j],ft[i-1][j-w[i]]+p[i]);
        }
    }
}

//回溯寻找最优解向量
void traceback(int x[],int n,int ft[][MAXN],int V)
{
    //基本思路就是在最优解成立情况下，如果i物品被放进背包(即x[i] = 1)
    //那么ft[i][V]就是对应的最优子结构，这样给剩下物品提供的总体积减少w[i]
    //如果i物品不放进背包那么x[i] = 0，当然给剩下物品的总体积不变
    for(int i=1;i<=n;i++){
        //这一步比较就是来说明i物品有没有放进去
        //如果放进去f[i][V]和f[i-1][V]肯定是不会相同的
        if(ft[i][V]==ft[i-1][V])
            x[i] = 0;
        else{
            x[i] = 1;
            V-=w[i];
        }
    }
}