46. 攜帶研究材料（第六期模擬筆試）
題目描述
小明是一位科學(xué)家，他需要參加一場(chǎng)重要的國(guó)際科學(xué)大會(huì)，以展示自己的最新研究成果。他需要帶一些研究材料，但是他的行李箱空間有限。這些研究材料包括實(shí)驗(yàn)設(shè)備、文獻(xiàn)資料和實(shí)驗(yàn)樣本等等，它們各自占據(jù)不同的空間，并且具有不同的價(jià)值。?
小明的行李空間為 N，問小明應(yīng)該如何抉擇，才能攜帶最大價(jià)值的研究材料，每種研究材料只能選擇一次，并且只有選與不選兩種選擇，不能進(jìn)行切割。
輸入描述
第一行包含兩個(gè)正整數(shù)，第一個(gè)整數(shù) M 代表研究材料的種類，第二個(gè)正整數(shù) N，代表小明的行李空間。
第二行包含 M 個(gè)正整數(shù)，代表每種研究材料的所占空間。?
第三行包含 M 個(gè)正整數(shù)，代表每種研究材料的價(jià)值。
輸出描述
輸出一個(gè)整數(shù)，代表小明能夠攜帶的研究材料的最大價(jià)值。
輸入示例
6 1 2 2 3 1 5 2 2 3 1 5 4 3輸出示例
5提示信息
小明能夠攜帶 6 種研究材料，但是行李空間只有 1，而占用空間為 1 的研究材料價(jià)值為 5，所以最終答案輸出 5。?
數(shù)據(jù)范圍：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空間和價(jià)值都小于等于 1000
狀態(tài)：完成
思路：這是一個(gè)存粹的0-1背包的入門問題，先用二維的dp數(shù)組解決，dp[i][j]表示背包最大容量為j的時(shí)候從物品【0-i】任取，所以最后一個(gè)格就是背包容量是N時(shí)的最大價(jià)值，狀態(tài)轉(zhuǎn)移方程也是很好理解的dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i]),意思就是對(duì)比不取物品i時(shí)在這個(gè)容量時(shí)的最大價(jià)值和取這個(gè)物品在背包容量允許的情況下的價(jià)值。該題也是要初始化，dp[0][i]表示取物品0的最大價(jià)值。二維數(shù)組時(shí)先遍歷物品還是背包容量都是可以的。
可以從上面的二維數(shù)組思路中看出狀態(tài)轉(zhuǎn)移的時(shí)候其實(shí)就是把dp[i-1]行的與dp[i-1][j-weights[i]]+values[i]進(jìn)行對(duì)比所以我們可以直接用一個(gè)一維數(shù)組解決問題，這個(gè)數(shù)組中dp[i]表示背包容量為i的最大價(jià)值，轉(zhuǎn)移方程與二維數(shù)組的基本一致就是dp[i]跟dp[i-weights[i]]+values[i]進(jìn)行對(duì)比，但這里只能從大到小進(jìn)行容量的遍歷，因?yàn)槿绻〉酱髣t會(huì)重復(fù)加了。
dp二維數(shù)組：
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
String l1=sc.nextLine();
int M=Integer.valueOf(l1.split(" ")[0]),N=Integer.valueOf(l1.split(" ")[1]);
int[] weights=new int[M];
int[] values=new int[M];
for(int i=0;i<M;i++){
weights[i]=sc.nextInt();
}
for(int i=0;i<M;i++){
values[i]=sc.nextInt();
}
int[][] dp=new int[M][N+1];
for(int i=0;i<=N;i++){
if(weights[0]<=i)
dp[0][i]=values[0];
}
for(int i=1;i<M;i++){
for(int j=1;j<=N;j++){
if(j-weights[i]<0) dp[i][j]=dp[i-1][j];
else dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i]);
}
}
System.out.println(dp[M-1][N]);
}
}?dp一維數(shù)組：
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
String l1=sc.nextLine();
int M=Integer.valueOf(l1.split(" ")[0]),N=Integer.valueOf(l1.split(" ")[1]);
int[] weights=new int[M];
int[] values=new int[M];
for(int i=0;i<M;i++){
weights[i]=sc.nextInt();
}
for(int i=0;i<M;i++){
values[i]=sc.nextInt();
}
int[] dp=new int[N+1];
for(int i=0;i<M;i++){
for(int j=N;j>0;j--){
if(j-weights[i]<0) break;
dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);
}
}
System.out.println(dp[N]);
}
}416. 分割等和子集
給你一個(gè)?只包含正整數(shù)?的?非空?數(shù)組?
nums?。請(qǐng)你判斷是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。示例 1：
輸入：nums = [1,5,11,5] 輸出：true 解釋：數(shù)組可以分割成 [1, 5, 5] 和 [11] 。示例 2：
輸入：nums = [1,2,3,5] 輸出：false 解釋：數(shù)組不能分割成兩個(gè)元素和相等的子集。提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
狀態(tài)：沒想出來
思路：這個(gè)是恰好相等類的問題，這里的物品質(zhì)量跟物品價(jià)格都一致，我們使用一維dp數(shù)組去解決這個(gè)問題，dp[i]表示和為i時(shí)的最大數(shù)值，這題明顯只有和為數(shù)組和的半時(shí)才能得到兩個(gè)相等和的子數(shù)組。所以最后只要dp[target]==target表示存在這樣的子數(shù)組。文章來源：http://www.zghlxwxcb.cn/news/detail-856146.html
class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int a:nums){
sum+=a;
}
if(sum%2==1) return false;
int target=sum/2;
int[] dp =new int[target+1];
for(int i=0;i<nums.length;i++){
for(int j=target;j>=0;j--){
if(j-nums[i]<0) break;
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[target]==target;
}
}?文章來源地址http://www.zghlxwxcb.cn/news/detail-856146.html
到了這里，關(guān)于Day39 代碼隨想錄(1刷) 動(dòng)態(tài)規(guī)劃 0-1背包的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
