23.01 가방의 귀환 소환 & 동적 기획
11503 단어 데이터 구조 및 알고리즘
public class HuiSuBag {
//
private static int maxW = Integer.MIN_VALUE; // maxW
private int[] weight = {2, 2, 4, 6, 3}; //
private int w = 9; //
public static void main(String[] args) {
new HuiSuBag().f(0,0);
System.out.println(maxW);
}
public void f(int i, int cw) { // f(0, 0)
if (cw == w || i == weight.length) { // cw==w ,i==weight.length
if (cw > maxW) {
maxW = cw;
}
return;
}
f(i + 1, cw); // i
if (weight[i] + cw <= w) {
f(i + 1, cw + weight[i]);
}
}
public int dp() {
int[][] dp = new int[weight.length][w + 1];
dp[0][0] = 1;
dp[0][weight[0]] = 1;
for (int i = 1; i < weight.length; i++) {
for (int j = 0; j < w + 1; j++) {
if (dp[i - 1][j] == 1) {
dp[i][j] = 1;
if (j + weight[i] <= w) {
dp[i][j + weight[i]] = 1;
}
}
}
}
int result = 0;
for (int i = w; i >= 0; i--) {
if (dp[weight.length - 1][i] == 1) {
result = Math.max(result, i);
}
}
return result;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 1000 개 노크 #6. ZigZag ConversionProblem 문제는 에서 빌리고 있지만, 예제를 보는 한 Paypal의 인터뷰에서 출제 된 것이 있다고 추측됩니다. Solution 지그재그에 나열한 다음 각 행을 t0 , t1 , t1 . 파이썬 버전 코드: 계...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.