主題描述
明是一位科學家，他需要參加一個重要的國際科學會議來展示他的最新研究成果。他需要帶一些研究資料，但他的行李箱空間有限。這些研究資料包括實驗設備、文獻、實驗樣本等，各自佔據不同的空間，具有不同的價值。
Ming的行李空間為N，請問Ming應該如何選擇攜帶最有價值的研究資料。每個研究材料只能選擇一次，並且只有選擇或不選擇兩種選擇，並且不能進行剪切。
輸入說明
第一行包含兩個正整數，第一個整數M代表研究材料的類型，第二個正整數N代表Ming的行李空間。
第二行包含 M 個正整數，代表每種研究材料所佔用的空間。
第三行包含M個正整數，代表每個研究資料的價值。
輸出描述
輸出一個整數，代表Ming可以攜帶的研究材料的最大值。
輸入範例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
輸出範例
5
提示
小明可以攜帶6個研究材料，但行李空間只有1個，而佔用1個空間的研究材料價值5個，所以最終答案是輸出5。
資料範圍：
1
1
研究資料佔用空間和研究資料價值均小於等於1000。
public class Main{
public static void main (String[] args) {
/* code */
Scanner s = new Scanner(System.in);
int M = s.nextInt();
int N = s.nextInt();
// clear buffer symbol /n
s.nextLine();
String w = s.nextLine();
String v = s.nextLine();
int[] weight = Arrays.stream(w.split(" "))
.mapToInt(Integer::valueOf)
.toArray();
int[] value = Arrays.stream(v.split(" "))
.mapToInt(Integer::valueOf)
.toArray();
int[][] dp = new int[M][N+1];
for(int i=weight[0]; i<=N; i++){
dp[0][i] = value[0];
}
for(int i=1; i<M; i++){
for(int j=1; j<=N; j++){
if(weight[i] > j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
System.out.println(dp[M-1][N]);
}
}
1，dp陣列意味著我們可以得到item i和目標bag size j的最大值。行表示物品，列表示包的尺寸。
2，對於init，我們初始化第一行和第一列（但實際上我們預設初始化列為0，這意味著）
3，迴歸關係為：對於每一項：
a、如果物品的重量大於包包的尺寸，則無法選擇該物品，目前尺寸為先前選擇的物品集合的尺寸。
b、如果物品的重量可以，我們必須比較先前選擇的物品的集合的大小減去當前物品的大小（如果我們不這樣做，則總大小將是大小+ 大小當前項目的，它將破壞我們的dp數組的邏輯）。
這裡，是雙循環的順序，因為我們可以用一個二維數組來記錄所有結果，並從上一行中找到當前行。
for(int i=1; i<M; i++){
for(int j=1; j<=N; j++){
if(weight[i] > j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
int[] dp = new int[target+1];
for(int i=1; i<nums.length; i++){
for(int j=target; j>=1; j--){
if(nums[i] > j){
continue;
}
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
}
}
給定一個整數數組 nums，如果可以將數組分成兩個子集，使得兩個子集中的元素總和相等，則傳回 true，否則傳回 false。
範例1：
輸入：nums = [1,5,11,5]
輸出：true
說明：陣列可分為 [1, 5, 5] 和 [11]。
範例2：
輸入：nums = [1,2,3,5]
輸出：假
解釋：陣列不能分割為等和子集。
限制：
1
1
原始頁
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if(sum%2==1){
return false;
}
int target = sum>>1;
int[][] dp = new int[nums.length][target+1];
for(int i=nums[0]; i<=target; i++){
dp[0][i] = nums[0];
}
for(int i=1; i<nums.length; i++){
for(int j=1; j<=target; j++){
if(nums[i] > j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
}
}
}
return dp[nums.length-1][target] == target;
}
以上是LeetCode Day動態程式設計第 3 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！
