装载问题之一
#include <stdio.h>#include <stdlib.h>#define MAXSIZE 100int 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); }}