Java 구현 로곡 P1049 포장 문제
1530 단어 낙곡
nn개 물품 중 몇 개를 상자에 넣고 상자의 남은 공간을 최소화하도록 요구합니다.
입력 출력 형식 입력 형식: 상자 용량을 나타내는 정수 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 =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]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
낙곡-훈련장-초보촌-과정함수와 귀속-P1036선수설명: n에서 k개의 수를 구하는 것에 관하여 C(n,k)의 구체적인 추출법은 귀속으로 실현할 수 있다. 소수에 대한 판단:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
