程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 裝載問題之三

裝載問題之三

編輯:C++入門知識

 [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.2cto.com
        if (cw + r > bestw) 
        { 
            x[t] = 0; 
            backtrack(t + 1); 
        } 
        r += w[t]; 
    } 

作者:fcwr_zhuxin_fcwr

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved