装箱问题

题源

呼~动态规划、递归、记忆化搜索都能解，但是好像又被递归绕进去了
 

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。

现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 V，表示箱子容量。

第二行共一个整数 n，表示物品总数。

接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。

输出格式

• 共一行一个整数，表示箱子最小剩余空间。

输入输出样例

输入 #1复制

24
6
8
3
12
7
9
7

输出 #1复制

0

说明/提示

对于 100% 数据，满足 0<n≤30，1≤V≤20000。

动态规划，思想简单易懂

#include<bits/stdc++.h>
using namespace std;
int v,n;
int a[100]={0};
int dp[20005][20005]={0};
int main()
{
	
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=v;j++){
			if(j>=a[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
			}
			else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	
	cout<<v-dp[n][v];
	return 0;
}

接下来是递归

#include<bits/stdc++.h>
using namespace std;
int v,n;
int a[100]={0};
int dp[20005][20005]={0};
int sum=0;
int minn=9999999;
void dfs(int x,int v)
{
	minn=min(minn,v);
	if(x==n+1){
		return;
	}
	if(v>=a[x]){//空间有多余时可以得选 
		dfs(x+1,v-a[x]);
	}
	dfs(x+1,v);
	

    return;
}
int main()
{
	
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    dfs(1,v);
	
	cout<<minn;
	return 0;
}

然后是记忆化搜索

#include<bits/stdc++.h>
using namespace std;
int v,n;
int a[100]={0};
int dp[20005][20005]={0};
int sum=0;
int minn=9999999;
int dfs(int x,int v)
{
	if(x==0) return dp[x][v] ;
	if(dp[x][v]!=0) return dp[x][v]; 
    if(v>=a[x]) return dp[x][v]=max(dfs(x-1,v),dfs(x-1,v-a[x])+a[x]);
    return dp[x][v]=dfs(x-1,v);
}
int main()
{
	
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    cout<<v-dfs(n,v);
	return 0;
}