回溯算法求解轮船装载问题

【问题描述】

给定n个货箱,货箱i 重为 wi，船可以装载的货箱总重量为 W。货箱装载问题是在不超过载重量的前提下装载尽可能重的货箱。

装载问题的解可以用向量 (x1,x2,…,xn)表示，xi∈{0,1}, xi =1 表示货箱i被装上船， xi =0表示货箱 i不装上船。请设计一个基于回溯算法的装载问题的求解方案。

【输入】

第1行输入正整数n和船的装载重量W，第2行依次输入n个整数，表示n个货箱的重量。

【输出】

输出两行，第1行输出最大的装载重量，第2行输出解向量 (x1,x2,…,xn)。

【输入样例】

6 26

1 7 4 20 9 11

【输出样例】

1 0 1 1 0 0

static int[] x = new int[w.length];
static int[] bestx = new int[w.length];
static int bestw = Integer.MIN_VALUE;
static int cw = 0;
static int r = 0; // 记录物品i后面所有物品的总重量

public static void main(String[] args) {
    for (int i = 0; i < w.length; i++) {
        r += w[i];
    }
    backstrace(0);

    int sum = 0;
    for (int i = 0; i < bestx.length; i++) {
        if(bestx[i] == 0){
            sum += w[i];
        }
    }
    if(sum > c2){
        System.out.println("物品无法装载到轮船!");
        return;
    }

    System.out.println("C1:" + c1 + "装载物品:");
    for (int i = 0; i < bestx.length; i++) {
        if(bestx[i] == 1){
            System.out.print(w[i] + " ");
        }
    }
    System.out.println();

    System.out.println("C2:" + c2 + "装载物品:");
    for (int i = 0; i < bestx.length; i++) {
        if(bestx[i] == 0){
            System.out.print(w[i] + " ");
        }
    }
    System.out.println();
}

private static void backstrace(int i) {
    if(i == w.length){
        if(cw > bestw){
            bestw = cw;
            for (int j = 0; j < x.length; j++) {
                bestx[j] = x[j];
            }
        }
    } else {
        r -= w[i];
        if(cw + w[i] <= c1){
            cw += w[i];
            x[i] = 1;
            backstrace(i+1);  // 选择第i个节点
            cw -= w[i];
        }

        if(cw + r > bestw){
            x[i] = 0;      // 才有必要去往右边的i节点
            backstrace(i+1); // 没选择第i个节点
        }

        r += w[i];
    }
}
运行结果：

挺有意思的一类算法问题，待我研究研究

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

int * Loading(int c1,int w[],int n);// 返回最优解
void Backtrack(int* i,int *B,int *w,int *x);// 回溯
// record the best result
void record(int *rec,int *x,int n);// 记录最优解
void sort(int *num,int n);// 冒泡排序由大到小

int main()
{
	// 未按照顺序简历
    int W[7]={30,20,12,10,90,80,40};
    int c1=152,c2=130;
    int *res=Loading(c1,W,7);
    // 输出结果方案
    for(int i=0; i<7; i++)
        printf("%d\t",res[i]);b2
    return 0;
}

int * Loading(int c1,int w[],int n){
    sort(w,n);// 将载重量由大到小排序
    // x[i]表示第i个集装箱是否装入第一艘船
    // rec记录最优解
    int *x=(int*)malloc(n*sizeof(int));
    if(x==NULL) exit(0);
    int *rec=(int*)malloc(n*sizeof(int));
    if(rec==NULL) exit(0);
    for(int i=0; i<n; i++){
        x[i]=0;
        rec[i]=0;
    }
    // B表示当前第一艘船剩余载重空间，best表示最小的剩余载重空间
    // 求得best最小值即为求得使第一艘船载重最多的情况
    int B=c1,best=c1,i=0;
    do{
        while(i<n){
            // 如果装入后重量不超过C1
            if(B-w[i]>=0){
                B=B-w[i];
                x[i]=1;
            }else{
                x[i] = 0;
            }
            i++;
        }

        if(B<best){
            // 记录此时最优解
            record(rec,x,n);
            best=B;
        }
        // 回溯到可以分支的支点上
        Backtrack(&i,&B,w,x);
    }while(i!=0);
    return rec;
}
void Backtrack(int* i,int *B,int *w,int *x){
    while(*i>0 && x[*i]==0)  (*i)-=1;

    if(x[*i] == 1){
        x[*i]=0;
        *B+=w[*i];
        (*i)++;
    }
}
void record(int *rec,int *x,int n){
    for(int i=0;i<n;i++)
        rec[i]=x[i];
}
void sort(int *num,int n){
    // 冒泡排序
    int tmp;
    for(int i=n-1; i>0; i--)
        for(int j=0; j<i; j++){
            if(num[j]<num[j+1]){
                tmp=num[j];
                num[j]=num[j+1];
                num[j+1]=tmp;
            }
        }
}

您的问题已经有小伙伴解答了，请点击【采纳】按钮，采纳帮您提供解决思路的答案，给回答的人一些鼓励哦～～

ps:开通问答VIP，享受5次/月有问必答服务，了解详情↓↓↓

【电脑端】戳>>> https://vip.csdn.net/askvip?utm_source=1146287632
【APP 】戳>>> https://mall.csdn.net/item/52471?utm_source=1146287632