洛谷P1049 [NOIP2001 普及组] 装箱问题，全网最详细的JAVA题解

洛谷P1049 [NOIP2001 普及组] 装箱问题，全网最详细的JAVA题解 题目

题解1: DFS

public class Main {
	
	private static int capacity;//容器容量
	private static int num;//物体数量
	private static int[] data;//物体体积数组
	private static boolean[] flages;//标记该物体是否已经加入容器中，避免重复加入
	private static int minDistance=0;//物品最终最接近容器的体积（不超过容器容积的前提下）
	private static boolean flage=false;//为true时，说明已经找到物品最终体积=容器容积,没必要再进行递归了
	public static void main(String[] args) {
		//数据输入
		Scanner in=new Scanner(System.in);
		capacity=in.nextInt();
		num=in.nextInt();//数量
		data=new int[num];
		flages=new boolean[num];
		for (int i = 0; i < data.length; i++) {
			data[i]=in.nextInt();
		}
		in.close();
		DFS(0,0);//调用深搜的方法
		if(!flage) System.out.println(capacity-minDistance);//找到物品最终体积=容器容积,则打印minDistance
	}
	private static void DFS(int i,int weights) {
		if(i>=num || weights>capacity || flage) return;
		if(weights==capacity) {//找到物品最终体积=容器容积
			flage=true;//标记为true,说明已经找到物品最终体积=容器容积
			System.out.println(0);
			return;
		}
		minDistance=Math.max(weights, minDistance);//在体积小于capacity，minDistance的最大值
		for (int j = i; j < data.length; j++) {
			if(flages[j]) continue;
			flages[j]=true;//标记该物体是否已经加入容器中，避免重复加入
			DFS(i++, weights+data[j]);
			flages[j]=false;
		}
	}
}

时间：589ms 空间：17.56MB

题解2 动态规划

这是一道0—1背包问题的变形

变量说明与定义状态
capacity ：容量
num：物品数量
dp[i][j] 表示前i个商品前提下，最大体积为j的前提下，dp[i][j]最接近capacity时的体积
data[i]物品i的体积

public class Main {
	
	public static void main(String[] args) {
		//数据输入
		Scanner in=new Scanner(System.in);
		int capacity=in.nextInt();//容量
		int num=in.nextInt();//数量
		int[] data=new int[num];
		for (int i = 0; i < data.length; i++) {
			data[i]=in.nextInt();
		}
		in.close();
		
		//dp[i][j] 表示前i个商品前提下，最大重量为j的前提下，  dp[i][j]最接近capacity时的重量
		int[][] dp=new int[num+1][capacity+1];
		for (int i = 1; i <= num; i++) {
			for (int j = 1; j <= capacity; j++) {
				if(data[i-1]>j) {
					dp[i][j]=dp[i-1][j];
				}else {
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-data[i-1]]+data[i-1]);
				}
			}
		}
		System.out.println(capacity-dp[num][capacity]);
	}
}

时间：373ms 空间：19.10MB

题解3 题解2空间优化

上述代码的dp数组使用的空间为O(n^2),可以优化为O(n)
最大体积为j的前提下，dp[j]最接近capacity时的体积

public class P1049装箱问题_DP2 {
	
	public static void main(String[] args) {
		//数据输入
		Scanner in=new Scanner(System.in);
		int capacity=in.nextInt();//容量
		int num=in.nextInt();//数量
		int[] data=new int[num];
		for (int i = 0; i < data.length; i++) {
			data[i]=in.nextInt();
		}
		in.close();
		
		//最大体积为j的前提下，dp[j]最接近capacity时的体积
		int[] dp=new int[capacity+1];
		for (int i = 1; i <= num; i++) {
			for (int j = capacity; j >=data[i-1]; j--) {
				dp[j]=Math.max(dp[j], dp[j-data[i-1]]+data[i-1]);
			}
		}
		System.out.println(capacity-dp[capacity]);
	}

}

时间：379ms 空间：18.00MB