装载.txt

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· 文本 代码 · 共 58 行

#include <iostream>
using namespace std ;
const int N = 20 ;
int w[20] ;//集装箱重量数组
int c ;  //第一艘船的载重量
int cw = 0 ;//当前载重量
int bestw  = 0 ;//当前最优载重量
int bestx[20];
int x[20] ;
int r ;//剩余载重量
int n ;

void backtrack(int i) 
{
	if( i == n) 
	{
		for(int i = 0; i < n ; i ++)
			bestx[i] = x[i] ;
		bestw = cw ;
		return ;
	}

	r -= w[i] ;
	if( cw + w[i] <= c)
	{
		x[i] = 1 ;
		cw += w[i] ;
		backtrack(i + 1) ;
		cw -= w[i] ;
	}
	if(cw + r > bestw)//剪枝
	{
		x[i]  = 0 ;
		backtrack(i + 1) ;
	}
	r += w[i] ;
}

		
  int main()
{
	int i ;
//	freopen("in.txt","r",stdin) ;
	cin >> n ; 
	for( i =  0; i < n ;i ++) 
		cin >> w[i] ;
	cin >> c ;
	cw = 0 ;
	bestw  = 0 ;
	for( i = 0  ; i  < n ; i ++)
		r += w[i] ;
	backtrack(0) ; 
	cout << bestw << endl ;
	for( i = 0  ; i < n ; i ++)
		if(bestx[i] == 1) cout << w[i] << " " ;
	cout << endl ;
	return 1 ;
}