装载问题之三

 [cpp]/*
    构造最优解
*/ 
#include <stdio.h> 
#include <stdlib.h> 
#define MAXSIZE 100 
int n;                      //集装箱个数 
int c;                      //容量 
int w[MAXSIZE];             //集装箱重量 
int r;                      //剩余重量 
int cw;                     //当前重量 
int bestw;                  //最优重量 
int x[MAXSIZE];             //当前解 
int bestx[MAXSIZE];         //最优解 
void input(); 
void init(); 
void backtrack(int); 
int main(void) 
{ 
    int i = 0; 
    while (1) 
    { 
        input(); 
        init(); 
        backtrack(0); 
        printf("%d\n", bestw); 
        for (i = 0; i < n; ++i) 
        { 
            printf("%d ", bestx[i]); 
        } 
        printf("\n"); 
    } 
    return 0; 
} 
void input() 
{ 
    int i = 0; 
    printf("please enter n:"); 
    scanf("%d", &n); 
    printf("please enter c:"); 
    scanf("%d", &c); 
    for (i = 0;i < n; ++i) 
    { 
        scanf("%d", &w[i]); 
    } 
} 
void init() 
{ 
    int i = 0; 
    cw = 0; 
    bestw = 0; 
    for (i = 0; i < n; ++i) 
    { 
        r += w[i]; 
    } 
    for (i = 0; i < n; ++i) 
    { 
        x[i] = 0; 
    } 
} 
void backtrack(int t) 
{ 
    int i = 0; 
    if (t >= n) 
    { 
        if (cw > bestw) 
        { 
            bestw = cw; 
            for (i = 0; i < n; ++i) 
            { 
                bestx[i] = x[i]; 
            } 
        } 
    } 
    else 
    { 
        r -= w[t]; 
        cw += w[t]; 
        if (cw <= c) 
        { 
            x[t] = 1; 
            backtrack(t + 1); 
        } 
        cw -= w[t]; www.zzzyk.com
        if (cw + r > bestw) 
        { 
            x[t] = 0; 
            backtrack(t + 1); 
        } 
        r += w[t]; 
    } 
} 
作者：fcwr_zhuxin_fcwr

补充：软件开发 , C++ ,