0-1背包的动态规划，回溯，分支限界三种解法

0-1背包的动态规划，回溯，分支限界三种解法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int Traceback(int **map, int n, int *X, int Max_Weight, int *Weight);
int Knaspack(int *Weight, int * Value, int Max_Weight, int n, int **map);
int max(int m,int n);
int min(int m,int n);
int main()
{
    int i;
    int Weight[] = {0,2,2,6,5,4};           //一维数组，存有每个物品的重量，Weight[0]存为0，无实际意义。
    int Value[] = {0,6,3,5,4,6};            //一维数组，存有每个物品的价值，同上。
    int Max_Weight = 10;                    //背包所能放的最大重量。

    int n = sizeof(Weight) / sizeof(Weight[0]) - 1; //n:物品的个数。

    int **map =(int **)malloc(sizeof(int *) * (n + 1));   //二维数组map作为地图，行数为n+1，列数为Max_Weight+1;
    for(i = 0;i < n + 1;i++){
        map[i] = (int *)malloc(sizeof(int) * (Max_Weight + 1));
    }

    int *X = (int *)malloc(sizeof(int) * (n + 1));    //一维数组X存储结果

    Knaspack(Weight, Value, Max_Weight, n, map);           //填表

    Traceback(map, n, X, Max_Weight, Weight);      //由表得出结果

    for(i = 1; i <= n; i++){
         printf("第%d个：%2d\n", i, X[i]);      //打印结果
    }

    printf("%d\n",map[1][Max_Weight]);

    return 0;

}

int Knaspack(int *Weight, int * Value, int Max_Weight, int n, int **map)
{
     int i,j;
     int jMax = min(Weight[n] - 1,Max_Weight);     //先开始填表的最后一行，即：先开始考虑第n个物品拿不拿。此处，选取两者中的最小为拿不拿第n个物品的分界点。

     for(j = 0; j <= jMax; j++){      //此处为不能拿第n个物品时，所得的价值为0.
          map[n][j] = 0;
     }

     for(j = Weight[n]; j < Max_Weight; j++){  //此处为拿第n个物品时，所得价值为Vanlue[n];
          map[n][j] = Value[n];
     }

     for(i = n - 1; i > 1; i--){
          jMax = min(Weight[i] - 1, Max_Weight); //能不能拿第i个物体的分界
          for(j = 0; j <= jMax; j++){
               map[i][j] = map[i+1][j];     //不能拿时所得价值维持不变
          }
          for(j = Weight[i]; j <= Max_Weight; j++){
              map[i][j] = max(map[i + 1][j], map[i + 1][j - Weight[i]] + Value[i]); //比较两者，前者为选择不拿此物品所能得的价值，后者为拿此物品所得的价值，相比较取最大。
          }
     }

     map[1][Max_Weight] = map[2][Max_Weight];
     if(Max_Weight >= Weight[1]){
         map[1][Max_Weight] = max(map[1][Max_Weight],map[2][Max_Weight - Weight[1]] + Value[1]);
     }
}

int max(int m,int n)
{
    if(m < n){
        return n;
    }else{
        return m;
    }
}
int min(int m,int n)
{
    if(m < n){
         return m;
    }else{
        return n;
    }
}

int Traceback(int **map, int n, int *X, int Max_Weight, int *Weight)
{
     int i;
     for(i = 1; i < n; i++){
         if(map[i][Max_Weight] == map[i + 1][Max_Weight]){   //如果这两个数相等则说明没有拿此物品
             X[i] = 0;
         }
         else{
              X[i] = 1;
              Max_Weight -= Weight[i];
         }
     }
     X[n] = (map[n][Max_Weight])? 1 : 0;
}

#include<iostream>

using namespace std;

float Knapsack(float *p, int *w , int c, int n);
int Sort(float *p, int *w, int n);
class Knap{                     //每个节点
    friend float Knapsack(float *, int *, int, int);
    private:
        float Bound(int i);
        void Backtrack(int i);
        int c;      //背包容量
        int n;        //物品数
        int *w;     //物品重量数组
        float *p;     //物品价值数组
        int cw;     //当前重量
        float cp;     //当前价值
        float bestp;  //当前最优价值
};

void Knap::Backtrack(int i)
{
    if (i > n){                 //到达叶节点
        bestp = cp;
        return;
    }

    if(cw + w[i] <= c){        //如果当前重量加上第i个物品的重量还未超重，那么可以进入左子树，即决定拿第i个物品。
         cw += w[i];           //此时当前重量变化，当前价值也变化
         cp += p[i];
         Backtrack(i + 1);     //装上第i个商品时再继续向树的下方走
         cw -= w[i];          //当前的重量，价值恢复，为了在判断右子树时参数都正确。
         cp -= p[i];
    }

    if(Bound(i + 1) > bestp){   //如果右子树的上界大于当前最优价值，那么进入右子树。
         Backtrack(i + 1);
    }
}

float Knap::Bound(int i)   //计算上界
{
     int cleft = c - cw;     //计算剩余容量
     float b = cp;          //记录当前价值

     while(i <= n && w[i] <= cleft){      //以物品单位重量递减的顺序装入商品。
          cleft -= w[i];
          b += p[i];
          i++;
     }
     if (i <= n){
          b += p[i] * cleft / w[i];     //将能装的最后一个物品装入一部分，此时将背包装满，为上界。
     }

     return b;
}

float Knapsack(float *p, int *w , int c, int n)
{
    int i,j;
    Sort(p,w,n);
    Knap K;

    K.p = new float[n + 1];
    K.w = new int[n + 1];
    for(i = 1; i < n; i++){
         K.p[i] = p[i];
         K.w[i] = w[i];
    }
    K.cp = 0;
    K.cw = 0;
    K.c = c;
    K.n = n;
    K.bestp = 0;

    K.Backtrack(1);

    delete []K.w;
    delete []K.p;

    return K.bestp;
}

int Sort(float *p, int *w, int n)   //排序函数(冒泡)
{
     int i,j,swap;

     for(i = 1; i < n; i++){
         swap = 0;
         for(j = 1; j <= n - i; j++){
             if((p[j] / w[j]) < (p[j+1] / w[j+1])){
                 w[0] = w[j];
                 p[0] = p[j];

                 w[j] = w[j+1];
                 p[j] = p[j+1];

                 w[j+1] = w[0];
                 p[j+1] = p[0];

                 swap = 1;
             }

         }
             if(swap == 0){
                  break;
             }
     }

     for(i = 1; i <= n; i++){
            cout << (p[i]/w[i])<<endl;
     }
}


int main()
{
     int i,j;
     int Weight[] = {0,2,2,6,5,4};
     float value[] = {0,6,3,5,4,6};

     int Max_Weight = 10;

     int n = sizeof(Weight) / sizeof(Weight[0]) - 1;

     float answer = Knapsack(value,Weight,Max_Weight,n);

     cout<<answer<<endl;

     return 0;

}