问题标题: 1049   装载问题

1049   装载问题

经验值：1600 时间限制：1000毫秒 内存限制：128MB

题目描述 Description

有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

输入描述 Input Description

第一行有2个正整数n和c。n是集装箱数，c是轮船的载重量。接下来的1行中有n个正整数，表示集装箱的重量。

输出描述 Output Description

计算出的最大装载重量

样例输入 Sample Input

5 10 7 2 6 5 4

样例输出 Sample Output

10

数据范围及提示 Data Size & Hint

n<=40，c<=1000

错误代码 TLE 37分：

#include<bits/stdc++.h>
using namespace std;
int n,v,a[45],mx;
bool b[45];
void dfs(int x){
	if(x==n+1){
		int s=0;
		for(int i=1;i<=x;i++){
			if(b[i]){
//				cout<<a[i]<<' ';
				s+=a[i];
			}
		}
//		cout<<endl;
		if(s<=v){
			mx=max(mx,s);
		}
		return ;
	}
	b[x]=1;
	dfs(x+1);
	b[x]=0;
	dfs(x+1);
}
int main(){
	cin>>n>>v;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1);
	cout<<mx;
	return 0;
}

用了搜索，结果TLE，求大佬指点！！！

熊潇然在2022-11-06 20:48:09追加了内容

为了方便大佬们复制代码，我就用了代码分享

熊潇然在2022-11-06 21:17:23追加了内容

@姜宇轩 emmm......不会

#include<bits/stdc++.h>
using namespace std;
int n,v,a[45],mx;
bool b[45][45];
void dfs(int x,int u){
	if(b[i][j]!=-1){
		//返回b[i][j]
		//return b[i][j]？？？ 
	}
	//听得好绕，递归并不怎么会，不会写 
}
int main(){
	cin>>n>>v;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			b[i][j]=-1;
		}
	}
	dfs(1,1);
	cout<<mx;
	return 0;
}
 

熊潇然在2022-11-07 09:33:10追加了内容

@姜宇轩 样例都没过，应该是我哪里理解错了

#include<bits/stdc++.h>
using namespace std;
int n,v,a[45];
int b[45][1005];
int f(int i,int j){
	if(b[i][j]!=-1){
		return b[i][j];
	}
	if(i==0){
		return 0;
	}
	if(a[i]<=j){
		b[i][j]=f(i-1,j-a[i])+a[i];
	}else{
		b[i][j]=f(i-1,j);
	}
}
int main(){
	cin>>n>>v;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	memset(b,-1,sizeof(b));
	cout<<f(n,v);
	return 0;
}