装载问题之二

 [cpp]/*
    上界函数
*/ 
#include <stdio.h> 
#include <stdlib.h> 
#define MAXSIZE 100 
//全局变量 
int n;                  //集装箱个数 
int c;                  //容量 
int r;                  //剩余容量 
int w[MAXSIZE];         //集装箱重量 
int cw;                 //当前重量 
int bestw;              //最优重量 
//输入函数 
void input(); 
//初始化函数 
void init(); 
//回溯法 
void backtrack(int); 
 
int main(void) 
{ 
    while (1) 
    { 
        input(); 
        init(); 
        backtrack(0); 
        printf("%d\n", bestw); 
    } 
    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]; 
    } 
} 
//回溯法 
void backtrack(int t) 
{ 
    if (t >= n) 
    { 
        if (cw > bestw) 
        { 
            bestw = cw; 
        } 
    } 
    else 
    { 
        //左子树 
        r -= w[t]; 
        cw += w[t]; 
        if (cw <= c) 
        { 
            backtrack(t + 1); 
        } 
        //右子树 
        cw -= w[t]; 
        if (cw + r > bestw) 
        { 
            backtrack(t + 1); 
        } 
        r += w[t]; 
    } 
} 

作者：fcwr_zhuxin_fcwr

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