題目描述

有一個箱子容量為V(正整數0≤V≤20000)，同時有n個物品(0

要求nn個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。

輸入輸出格式

輸入格式：

1個整數，表示箱子容量

1個整數，表示有n個物品

接下來n行，分別表示這n個物品的各自體積

輸出格式：

1個整數，表示箱子剩余空間。

輸入輸出樣例

輸入樣例#1：

24

6

8

3

12

7

9

7

輸出樣例#1：

0

這里先介紹最經典的動態規劃

下面還有一個簡化版的

import java.util.Scanner;

public class zhuangxiangwenti {

public static void main(String[] args) {

Scanner sc =new Scanner(System.in);

int v = sc.nextInt();

int n = sc.nextInt();

int [] num = new int [n+1];

for (int i = 1; i < num.length; i++) {

num[i]=sc.nextInt();

}

int [] [] dp = new int[n+1][v+1];

int min = Integer.MAX_VALUE;

for (int i = 1; i < n+1; i++) {

for (int j = 1; j

if(j>=num[i]){

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-num[i]]+num[i]);

}

else{

dp[i][j]=dp[i-1][j];

}

}

min = Math.min(min, v-dp[i][v]);

}

System.out.println(min);

}

}

import java.util.Scanner;

public class zhuangxiangwenti2 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int w = sc.nextInt();

int n = sc.nextInt();

int[] ff = new int[n];

for (int i = 0; i < ff.length; i++) {

ff[i] = sc.nextInt();

}

int[] t = new int[w + 1];

for (int i = 0; i < n; i++) {

for (int j = w; j >= 0; j--) {

if (j >= ff[i]) {

t[j] = Math.max(t[j], t[j - ff[i]] + ff[i]);

}

}

}

System.out.println(w - t[w]);

}

}

總結

以上是生活随笔為你收集整理的联机装箱问题 java_Java实现 洛谷 P1049 装箱问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。