欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷--P1049 装箱问题

程序员文章站 2024-02-29 16:52:52
...

洛谷--P1049 装箱问题
——————————————————————————————————————————————————
0-1背包问题
状态定义:
dp[i][j] 表示只考虑前 i 个物品,物品总体积 <= j 的情况下,装的最大体积是多少
dp[i][j]怎么来呢?来自两种情况:
1.不选择第 i 个物品
dp[i][j] = dp[i - 1][j]
2.选择第 i 个物品
dp[i][j] = dp[i - 1][j - v[i]] + v[i] // 选第 i 个,体积上限就要从前 i-1 个物品中留出 i 的体积,再加上 i 的体积

dp的初始化,dp[i][0] = 0,dp[0][j] = 0

import java.util.Scanner;

public class Main {
	static int V;
	static int n;
	static int[] a;
	
 	public static void main(String[] args) {
 		Scanner sc = new Scanner(System.in);
 		V = sc.nextInt();
 		n = sc.nextInt();
 		a = new int[n + 1];
 		for(int i = 1;i <= n;i++) a[i] = sc.nextInt();
 		sc.close();
 		
 		int[][] dp = new int[n + 1][V + 1];
 		for(int i = 1;i <= n;i++) {//递推每件物品
 			for(int j = 0;j <= V;j++) {//递推每个体积
 				dp[i][j] = dp[i - 1][j];//不选第i件物品
 				//选第i件
 				if(j >= a[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);
 			}
 		}
 		System.out.println(V - dp[n][V]);
	}
}
相关标签: 洛谷刷题