[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
