[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
