算法設計與分析實驗四回溯法

執行個體1 采用回溯算法求解0-1背包問題

問題描述：給定n種物品和一背包，物品i的重量是wi，其價值是pi，背包的容量是M，問如何選擇裝入背包中的物品總價值最大？

例如：有n=4件物品要裝入背包，物品重量和價值如下：

算法設計與分析實驗四回溯法

背包容量限制是M=6，問如何選擇物品，使得不超重的情況下裝入背包的物品價值達到最大？

//
// Created by 拔牙不打麻藥 on 2021/6/5.
//
#include "stdio.h"

int num;//物品數量
double volume;//背包的容量
double value[100];//每個物品的價值
double weight[100];//每個物品的重量
double per[100];//每個物品的機關價值
int order[100];//物品的編号
int put[100] = {0};//每個編号對應的物品是否放入
double current_weight;//目前背包的重量
double current_value;//目前背包裡的價值
double best_value;//目前背包的最優價值

//用冒泡排序對機關價值進行從大到小的排序
void knapsack() {
    int i, j;
    int temp = 0;
    int temp_value = 0;
    int temp_weight = 0;
    int temp_order = 0;
    for (i = 1; i <= num; i++) {
        per[i] = value[i] / weight[i];
    }
    for (i = 1; i <= num - 1; i++) {
        for (j = i; j <= num; j++) {
            if (per[i] <= per[j]) {
                temp = per[j];
                per[j] = per[i];
                per[i] = temp; //冒泡排序排機關價值

                temp_value = value[j];
                value[j] = value[i];
                value[i] = temp_value;//價值排序跟着機關價值排序變動

                temp_order = order[j];
                order[j] = order[i];
                order[i] = temp_order;//編号排序跟着機關價值排序變動

                temp_weight = weight[j];
                weight[j] = weight[i];
                weight[i] = temp_weight;//重量排序跟着機關價值排序變動
            }
        }
    }
}

//回溯法
//當第1個放入時，current_value、current_weight分别加上第一個的價值、重量，然後進入backtrack(2)，檢測背包裡放不放的下第二個物品
//放得下的話，current_value、current_weight分别加上第三個的價值、重量，然後進入backtrack(3)，一直加到第五個物品，第五個物品能放入背包，
//進入backtrack(6)，但第6個放不進背包，并且此時還沒到最後一個物品，用bound函數預測可能下面還有物品會使價值大于目前價值，繼續向下，第7個
//也放不進背包，并且此時還沒到最後一個物品，用bound函數預測可能下面還有物品會使價值大于目前價值，繼續向下，直到循環完所有物品。然後開始回溯
//因為從第6個開始放不進背包，考慮不放第5個物品，從第六個物品開始檢查，如果第六個放的進，current_value、current_weight分别加上第六個的價值、重量，
//進入backtrack(7),第七個放不進，bound函數預測可能下面還有物品會使價值大于目前價值，繼續向下直到循環完所有物品。然後回溯到第6個物品不放入，檢測第七個物品
//是否放的進，放的進就進入backtrack(8)，第8個放不進，而bound預測值小于目前值，回溯到不放入第7個物品，但第八個還是放不進，此時隻能回溯到不放入第四個物品，以此類推。
void backtrack(int i) {
    double bound(int i);
    if (i > num) { //完成循環時，最佳價值就是目前價值
        best_value = current_value;
        return;
    }
    if (current_weight + weight[i] <= volume) {//如果背包容量放得下第i個時
        current_weight += weight[i]; //目前重量加上第i個的重量
        current_value += value[i]; //目前價值加上第i個的價值
        put[i] = 1; //标記第i個已放入
        backtrack(i + 1); //循環，檢視背包是否放得下第i+1個物品
        current_weight -= weight[i];
        current_value -= value[i];

    }

    if (bound(i + 1) > best_value) {
        backtrack(i + 1);
    }
}

//上界函數
double bound(int i) {
    double left_weight = volume - current_weight;
    double v = current_value;
    while (i <= num && weight[i] <= left_weight) { //從i開始如果第i個放的進就在估值v中加入i的價值，循環直到有一個物品放不進
        left_weight -= weight[i];
        v += value[i];
        i++;
    }

    if (i <= num) { //因為這個物品放不進，但還沒有循環完所有的物品，就認為上界函數是剩餘空間充滿了該物體的機關價值
        v += value[i] / weight[i] * left_weight;

    }
    return v;
}

int main() {
    setbuf(stdout,NULL);
    int i;
    printf("請輸入物品的數量和背包的容量：\n");
    scanf("%d %lf", &num, &volume);
    printf("請輸入每一個物品的重量和價值：\n");
    for (i = 1; i <= num; i++) {
        printf("第%d個物品的重量是：\n", i);
        scanf("%lf", &weight[i]);
        printf("第%d個物品的價值是：\n", i);
        scanf("%lf", &value[i]);
        order[i] = i;
    }
    knapsack();
    backtrack(1);
    printf("最大的價值為：%lf\n", best_value);
    printf("需要裝入的物品編号是：\n");
    for (int (i) = 1; (i) <= num; ++(i)) {
        if (put[i] == 1) {
            printf("%d\n", order[i]);
        }
    }
    return 0;
}

算法設計與分析實驗四回溯法

執行個體2 采用回溯算法求解最優裝載問題

問題描述：有一批共有 n 個集裝箱要裝上兩艘載重量分别為 c1 和 c2 的輪船，其中集裝箱 i 的重量為 w[i], 且重量之和小于(c1 + c2)。裝載問題要求确定是否存在一個合理的裝載方案可将這 n 個集裝箱裝上這兩艘輪船。如果有，找出一種裝載方案。

例如：當n=3,c1=c2=50,且w=[10,40,40]時，求解裝載方案。

//
// Created by 拔牙不打麻藥 on 2021/6/5.
//

#include "stdio.h"

int num;//集裝箱個數
int c1;//船1的容量
int c2;//船2的容量
int put[100] = {0};//哪些集裝箱已經放上船1了
int weight[100];//每個集裝箱的重量
int current_weight = 0;//目前的重量
int best_weight = 0;//c1最優重量
int best_weight2 = 0;//c2最優裝載重量

//回溯法
void backtrack(int i) {
    if (i > num) { //此時已經将物品循環一次了
        best_weight = current_weight;
        return;
    } else { //還沒将物品循環一次
        if (current_weight + weight[i] <= c1) { //當船1還放得下第i件物品時
            current_weight += weight[i]; //目前重量加上第i件物品的重量
            put[i] = 1; //當put[i]=1時說明把第i件物品放上船1
            backtrack(i + 1); //判斷第i+1件物品放不放的上船
            current_weight -= weight[i];//當運作到這一句時說明有一件産品u放不上船1，那麼從u-1開始回溯，即u-1不放上船1，是以current_weight要減去u-1的重量

        } else {
            put[i] = 0;
            backtrack(i + 1); //當第i件放不上船1時，進入下一個循環，看下面的物品有沒有能放上船的
        }
    }
}

int main() {
    setbuf(stdout, NULL);
    printf("請輸入集裝箱個數：\n");
    scanf("%d", &num);
    printf("請輸入船1的容量：\n");
    scanf("%d", &c1);
    printf("請輸入船2的容量：\n");
    scanf("%d", &c2);
    printf("請輸入每一個集裝箱的重量：\n");
    for (int j = 1; j <= num; j++) {
        printf("請輸入第%d個集裝箱的重量：\n", j);
        scanf("%d", &weight[j]);
    }

    backtrack(1);
    printf("船1的最優裝載方案為：\n");
    for (int i = 1; i <= num; i++) { //當put數組中值為1的下标就是要放上船1的物品
        if (put[i] != 0) {
            printf("%d ", i);
        }
    }
    printf("\n");
    printf("船1的最優裝載重量為：%d\n", best_weight);

    for (int i = 1; i <= num; i++) {
        if (put[i] == 0) { //當put數組中值為0的下标就是要放上船2的物品
            best_weight2 += weight[i];
        }
    }
    if (best_weight2 <= c2) { //判斷當put數組中值為0的下标就是要放上船2的物品是否超出了船2的承重
        printf("船2的最優裝載方案為：\n");
        for (int i = 1; i <= num; ++i) {
            if (put[i] == 0) {
                printf("%d ", i);
            }
        }
        printf("\n");
        printf("船2的最優裝載重量為：%d\n", best_weight2);
    } else {
        printf("這兩艘船不能裝下所有的集裝箱！");
    }
}

算法設計與分析實驗四回溯法

執行個體3 采用回溯算法求解幂集問題

問題描述：求含N個元素的集合的幂集。

例如，對于集合A={1,2,3},則A的幂集為 p(A)={{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},Φ}。

解題思路：回溯法的思路是按照某種規則對解空間進行周遊，由回溯法來求集合的幂集非常簡單，此問題的解即判斷在某個子集中是否加入某個元素，例如解{1,3}将1,3加入，而2不加入，可以将問題的解空間定義為如下一顆狀态樹：

算法設計與分析實驗四回溯法

紅色的直線表示是否加入1，左子樹表示加入1，右子樹表示不加入1，同樣綠色的直線表示是否加入2，左子樹表示加入2，右子樹表示不加入2，以此類推。

在算法實作過程中可以使用一個結果數組 res[]來表示在某次周遊過程中元素的加入情況，res[i]=0表示不加入元素，res[i]=1表示加入元素，檢查完所有元素後列印結果。

//
// Created by 拔牙不打麻藥 on 2021/6/6.
//

#include "stdio.h"
#include "algorithm"
using namespace std;

int num=0;//集合中有幾個數字
int a[100];//存放集合中的每一個數字
int finish[100]={-1};//表示集合中的某個數在幂集中是否存在
void display(int *finish){ //将用0，1表示的數組表達成幂集，1表示有這個數字
    printf("{");
    for (int i = 1; i <= num; ++i) {
        if(finish[i] == 1){
            printf("%d ",a[i]);
        }
    }
    printf("}\n");
}

//回溯法
void backtrack(int *finish, int n){
if(n > num){
    display(finish); //如果周遊了一遍就将finish數組的結果用集合中的數字表達出來
    return;
}
for(int i = 0;i < 2; i++){
    finish[n] = i;
    backtrack(finish, n+1);
}
}

int main(){
    setbuf(stdout, NULL);
    printf("請輸入集合内數字的個數：\n");
    scanf("%d",&num);
    printf("請輸入集合内的每一個數字：\n");
    for (int i = 1; i <= num; i++) {
        printf("請輸入第%d個數字：\n",i);
        scanf("%d",&a[i]);
    }
    backtrack(finish,1);
    return 0;
}

算法設計與分析實驗四回溯法

算法設計與分析實驗四回溯法

目錄

執行個體1 采用回溯算法求解0-1背包問題

執行個體2 采用回溯算法求解最優裝載問題

執行個體3 采用回溯算法求解幂集問題

繼續閱讀

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

回溯法迷宮求解

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希

算法設計與分析 實驗四 回溯法

目錄

執行個體1 采用回溯算法求解0-1背包問題

執行個體2 采用回溯算法求解最優裝載問題

執行個體3 采用回溯算法求解幂集問題

繼續閱讀

算法設計與分析實驗四回溯法