裝載問題之一

[cpp]
#include <stdio.h> 
#include <stdlib.h> 
#define MAXSIZE 100 
int n;                      //集裝箱的個數 
int c;                      //集裝箱的容量 
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() 
{ 
    cw = 0; 
    bestw = 0; 
} 
void backtrack(int t) 
{ 
    int i = 0; 
    if (t >= n) 
    { 
        if (cw > bestw) 
        { 
            bestw = cw; 
        } 
    } 
    else 
    { 
        //進入左子樹 
        cw += w[t]; 
        if (cw <= c) 
        { 
            backtrack(t + 1); 
        } 
 
        //進入右子樹 
        cw -= w[t]; 
        backtrack(t + 1); 
    } 
} 
作者：fcwr_zhuxin_fcwr