1024programmer Java 2.01 Java solution to the knapsack problem (dp)

2.01 Java solution to the knapsack problem (dp)

Java code:O(n^2)

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();//The number of items int m = scan.nextInt();//The volume of the backpack int []v = new int[n + 1]; //Volume :volumn ;Volume array int []w = new int[n +1];//Knapsack weight:weight ;Weight&#xff08 ; value of array int [][]dp = new int[n + 1][m + 1];//dp[i][j]: means The maximum value of the first i items in the backpack when the backpack volume is j for (int i = 0; i <n; i++) {v[i + 1] &#61 ; scan.nextInt();w[i + 1] = scan.nextInt();}scan.close();for(int i = 1; i <= n ; i++) {for(int j = 1; j v[i]) //When the volume of the i-th item is smaller than the volume of j(backpack) at this time, dp[i][j] can be placed in it = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);//The maximum value is the dp value when the i-th item is not placed and the dp value when the i-th item is placed The maximum value of the total value when i items are placed //The maximum value of the i-th item is placed - based on the volume of the first i-1 items, first remove the volume that the i-th item will occupy // At this time, dp[i - 1][j - w[i]] represents the maximum value of the first i-1 items while retaining the volume of the i-th item // plus v[i] is the The maximum value of the i-th item}}System.out.println(dp[n][m]);}
}

Java code: O(n)

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int []v = new int[n + 1]; int []w = new int[n + 1];int []dp = new int[m + 1];for(int i = 1; i < = n; i++) {v[i] = scan.nextInt();w[i] = scan.nextInt();}scan.close() ;for(int i = 1; i = v[i]; j--) {//Traverse in reverse order , Ensure that the value of the previous round will not be overwritten dp[j] = Math.max(dp[j], dp[j - v[i]] & #43; w[i]); }}System.out.println(dp[m]);}
}

This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/2-01-java-solution-to-the-knapsack-problem-dp/

author: admin

Previous article
Next article

Leave a Reply

Your email address will not be published. Required fields are marked *

Contact Us

Contact us

181-3619-1160

Online consultation: QQ交谈

E-mail: [email protected]

Working hours: Monday to Friday, 9:00-17:30, holidays off

Follow wechat
Scan wechat and follow us

Scan wechat and follow us

Follow Weibo
Back to top
首页
微信
电话
搜索