NEFU算法设计与分析实验4

 回溯法解0-1背包问题

有n件物品和一个容量为c的背包。第i件物品的价值是v[i]，重量是w[i]。求解将哪些物品装入背包可使价值总和最大。所谓01背包，表示每一个物品只有一个，要么装入，要么不装入。

输入：

第1行是背包容量

第2行物品个数n

第3行：n个物品的重量

第4行：n个物品的价值

输出：

第1行：最优值

第2行：最优解

输入输出范例：

输入：

50   //背包容量

4   //物品个数

30 20 40 10    //物品重量

10 20 30 40    //物品价值

输出：

70    //最优值

0 0 1 1    //最优解

#include <iostream>
#define max 100
using namespace std;
int weight[max];
int value[max];
int n,max_weight,max_value;
int best_answer[max],answer[max];
int i,j,k,l;
void print()
{
    cout<<max_value<<endl;
    for(i=1;i<=n;i++)
        cout<<best_answer[i];
    cout<<endl;
}
int Bound(int level, int current_weight, int current_value) {
    int bound = current_value;
    int remaining_weight = max_weight - current_weight;
    for (int i = level + 1; i <= n; i++) {
        if (remaining_weight >= weight[i]) {
            bound += value[i];
            remaining_weight -= weight[i];
        } else {
            bound += (remaining_weight * 1.0 / weight[i]) * value[i];
            break;
        }
    }
    return bound;
}
void DFS(int level, int current_weight, int current_value) {
    if (level > n) {
        if (current_value > max_value) {
            max_value = current_value;
            for (int i = 1; i <= n; i++) {
                best_answer[i] = answer[i];
            }
        }
        return;
    }
    if (current_weight + weight[level] <= max_weight) {
        current_weight += weight[level];
        current_value += value[level];
        answer[level] = 1;
        DFS(level + 1, current_weight, current_value);
        current_weight -= weight[level];
        current_value -= value[level];
        answer[level] = 0;
    }
    if (Bound(level, current_weight, current_value) > max_value) {
        DFS(level + 1, current_weight, current_value);
    }
}
void init()
{
    max_value=0;
    for(i=1;i<=n;i++)
        answer[i]=0;
}
int main()
{
    cin>>max_weight>>n;
    for(i=1;i<=n;i++)
        cin>>weight[i];
    for(j=1;j<=n;j++)
        cin>>value[j];
    init();
    DFS(1,0,0);
    print();
    return 0;
}

回溯法解旅行售货员问题

设有一个售货员从城市1出发，到城市2，3，…，n去推销货物，最后回到城市1.假定任意两个城市i，j间的距离dij(dij=dji)是已知的，问他应沿着什么样的路线走，才能使走过的路线最短?

输入：

第1行城市个数n

从第2行开始输入任意两个城市之间距离的矩阵，没有道路的两个城市之间的距离为-1

输出:

第1行：最短距离

第2行：城市顺序

输入输出实例：

输入：

4      //城市个数

-1 30 6 4         //城市之间距离矩阵

30 -1 5 10

6 5 -1 20

4 10 20 -1

输出：

25    //最短距离

1 3 2 4    //

#include <iostream>

#define MAX_N 10
#define NO_PATH -1
#define MAX_WEIGHT 4000

using namespace std;

int N;
int City_Graph[MAX_N + 1][MAX_N + 1];
int x[MAX_N + 1];
int isIn[MAX_N + 1];
int bestw, cw, bw, bestx[MAX_N + 1];

void Travel_Backtrack(int t)
{
    int i, j;
    if(t > N)
    {
        bw = cw + City_Graph[x[N]][1]; 
        if(bw < bestw)
        {
            for(i = 1; i <= N; i++)
            {
                bestx[i] = x[i];
            }
            bestw = bw;
        }
        return;
    }
    else
    {
        for(j = 2; j <= N; j++)
        {
            if(City_Graph[x[t - 1]][j] != NO_PATH && !isIn[j])
            {
                isIn[j] = 1;
                x[t] = j;
                cw += City_Graph[x[t - 1]][j];
                Travel_Backtrack(t + 1);
                isIn[j] = 0;
                x[t] = 0;
                cw -= City_Graph[x[t - 1]][j];
            }
        }
    }
}

int main()
{
    int i, j;
    cin >> N;

    for(i = 1; i <= N; i++)
    {
        x[i] = 0;
        bestx[i] = 0;
        isIn[i] = 0;
    }
    x[1] = 1;
    isIn[1] = 1;
    bestw = MAX_WEIGHT;
    cw = 0;

    for(i = 1; i <= N; i++)
    {
        for(j = 1; j <= N; j++)
        {
            cin >> City_Graph[i][j];
        }
    }

    Travel_Backtrack(2);

    cout <<bestw << endl;

    for(i = 1; i <= N; i++)
    {
        cout << bestx[i] << " ";
    }
    cout << endl;

    return 0;
}