装载问题(多种方法解决)

问题描述
现要将n个重量为w[i]集装箱装到载重为c的轮船上，如何使得装载的集装箱重量最大

输入描述
第一行输入轮船载重量c和集装箱数量n
第二行输入n个集装箱的重量

输出描述
输出最大重量和集装箱编号

DFS

#include<cstdio>
#include<cstdlib> 
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const ll N=1e4+10; 
ll w[N];//集装箱重量 
ll flag[N];//当前解向量 
ll bestx[N];//最优解 
ll cw;//当前重量 
ll bestw;//最大重量 
ll r;//剩余集装箱重量 
ll n;//集装箱重量 
ll c;//轮船最大装载量 
void dfs(ll t)
{
	if(t>n)//叶子节点 
	{
		if(cw>bestw)//更新最优解 
		{
			for(int i=1;i<=n;i++)
				bestx[i]=flag[i];
			bestw=cw;
		} 
		return; 
	}
	r-=w[t];//剩余重量-- 
	if(c>=cw+w[t])//左子树 
	{
		flag[t]=1;//放入 
		cw+=w[t];//目前重量++ 
		dfs(t+1);//递归到子树 
		cw-=w[t];//还原 
	}
	if(cw+r>bestw)//右子树 
	{
		flag[t]=0;//不放入 
		dfs(t+1);//递归到子树 
	}
	r+=w[t];//还原 
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%lld %lld",&c,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&w[i]);
		r+=w[i]; 
	}
    dfs(1);
    printf("%lld\n",bestw);
    for(int i=1;i<=n;i++)
	{
		if(flag[i]==1)
			printf("%lld ",i);
	} 
    fclose(stdin);
    return 0;
}