01背包問題(二維數(shù)組和滾動(dòng)數(shù)組)
本題力扣上沒有原題，大家可以去卡碼網(wǎng)第46題?(opens new window)去練習(xí)，題意是一樣的。
《代碼隨想錄》算法視頻公開課?(opens new window)：帶你學(xué)透0-1背包問題！?(opens new window)，相信結(jié)合視頻再看本篇題解，更有助于大家對(duì)本題的理解。
這周我們正式開始講解背包問題！
背包問題的經(jīng)典資料當(dāng)然是：背包九講。在公眾號(hào)「代碼隨想錄」后臺(tái)回復(fù)：背包九講，就可以獲得背包九講的pdf。
但說實(shí)話，背包九講對(duì)于小白來說確實(shí)不太友好，看起來還是有點(diǎn)費(fèi)勁的，而且都是偽代碼理解起來也吃力。
對(duì)于面試的話，其實(shí)掌握01背包，和完全背包，就夠用了，最多可以再來一個(gè)多重背包。
看到題目的第一想法
? ? ? ?裝入背包的最大價(jià)值
? ? ? ? 維度
? ? ? ? 重量:weight
? ? ? ? 價(jià)值:value
? ? ? ? 背包容量：j
? ? ? ? 物品數(shù)量：i
看到代碼隨想錄之后的想法(二維數(shù)組)
? ? ? ?1 dp數(shù)組的定義和下標(biāo)的含義
? ? ? ? dp[i][j] 物品0~i之間能填入背包j的最大價(jià)值
? ? ? ? 2 確定遞推公式
? ? ? ? ?對(duì)于物品i 我們只有兩種選擇
? ? ? ? 1 若選擇物品i? 則最大值為 dp[i-1][j-weight[i]]+value[i]??
? ? ? ? 2 若不選擇物品i 則最大值為選擇上一個(gè)物品的最大值 dp[i-1][j]
? ? ? ? ?dp[i][j] =Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);?
??? ? ? 3 dp數(shù)組初始化
? ? ? ? 由于需要 i-1 的值 則需要把第一行初始化：
? ? ? ? 當(dāng)j<weight[i]? dp[0][j]=0
? ? ? ? 當(dāng)j>=weight[i] dp[0][j]=weight[i]
? ? ? ? 4 確定遍歷順序
? ? ? ? 先物品后背包
? ? ? ? 先背包后物品 都可以
? ? ? ? 5 舉例推導(dǎo)dp數(shù)組
自己實(shí)現(xiàn)過程中遇到的困難(二維數(shù)組)
? ? ? ?1 確定dp[i][j]時(shí),若weight[i]>j 則沒法取第二種情況，直接取第一種情況dp[i-1][j]
? ? ? ? 2 行列需要確認(rèn)好，最好畫圖
看到代碼隨想錄之后的想法(滾動(dòng)數(shù)組)
? ? ? ? 將二維數(shù)組壓縮成一維數(shù)組，只看一維數(shù)組中的內(nèi)容
? ? ? ? 當(dāng)選擇新的物品時(shí)，一維數(shù)組中的內(nèi)容，是上一層一維數(shù)組中的所有結(jié)果
? ? ? ?1 dp數(shù)組的定義和下標(biāo)的含義
? ? ? ? dp[j] 物品0~i之間能填入背包j的最大價(jià)值
? ? ? ? 2 確定遞推公式
? ? ? ? ?對(duì)于物品i 我們只有兩種選擇
? ? ? ? 1 若選擇物品i? 則最大值為 dp[j-weight[i]]+value[i]??
? ? ? ? 2 若不選擇物品i 則最大值為選擇上一個(gè)物品的最大值 dp[j]
? ? ? ? ?dp[i][j] =Math.max(dp[j],dp[j-weight[i]]+value[i]);?
??? ? ? 3 dp數(shù)組初始化
? ? ? ? 只有一行，全為0
? ? ? ? 4 確定遍歷順序
? ? ? ? 只能先物品后背包?
? ? ? ? 因?yàn)樽钚乱恍兄荒苋∩弦恍械膬?nèi)容來確認(rèn)，要確保每一行都處理完
? ? ? ? 且只能從后往前遍歷：如果從前往后，會(huì)把之前的數(shù)據(jù)打亂，而后續(xù)的數(shù)據(jù)需要依賴前面的數(shù)據(jù)
? ? ? ? 5 舉例推導(dǎo)dp數(shù)組
自己實(shí)現(xiàn)過程中遇到的困難(滾動(dòng)數(shù)組)
? ? ? ?1 確定dp[j]時(shí),若weight[i]>j 則沒法取第二種情況，直接取第一種情況
? ? ? ? 2 行列需要確認(rèn)文章來源：http://www.zghlxwxcb.cn/news/detail-802421.html
import java.util.*;
public class Main {
//卡哥做法：一維數(shù)組
//1 確認(rèn)dp數(shù)組，以及dp數(shù)組下標(biāo)的含義
// dp數(shù)組 一維數(shù)組 dp[j]
// 相當(dāng)于講二維數(shù)組進(jìn)行一個(gè)壓縮，每次只取最后一行(第i層)
// 一維數(shù)組都是利用上一層的結(jié)果推出第i層的值
// 下標(biāo)的含義 任意取物品0~i可存入空間為j的背包的最大值
//2 確定遞推公式
// 對(duì)于物品i 有兩種選擇 取兩者中的最大值
// 1 取物品i: 則當(dāng)前i j 的value 為 dp[i-1][j-weight[i]]+value[i]
// 一維數(shù)組： dp[j]=dp[j-weight[i]]+value[i]
// 2 不取物品i:則當(dāng)前 i j 的value 為dp[i-1][j];
// 一維數(shù)組: dp[j]=dp[j]
// 若weight[i]>j 則沒法取第一種情況，直接取第二種情況
// Math.max(dp[j],dp[j]-weight[j]);
//3 dp數(shù)組如何初始化
// dp[j] 的值來自 dp[j] dp[j-weight[i]]
// 若初始化，不能讓dp[j]過大，所以統(tǒng)一為最小非負(fù)數(shù)0
//4 確定遍歷順序
//從后往前，因?yàn)閖-weight[i] 是需要獲取這一行前面的值
//若從前往后，則會(huì)打亂上一層留下來的值 無法獲取正確的j-weight[i]值
// 按行列都可以
//5 舉例推導(dǎo)dp數(shù)組
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int size = sc.nextInt();
int[] value = new int[M];
int[] weight = new int[M];
for(int i = 0; i < M;i++) {
weight[i] = sc.nextInt();
}
for(int i = 0; i < M;i++) {
value[i] = sc.nextInt();
}
int[] dp = new int[size+1];
// 若比weight小則為0 若比weight大則為value
for(int i=0;i<=size;i++){
dp[i]=0;
}
//從i=0開始 也就是第0行就開始賦值
for(int i=0;i<weight.length;i++){
for(int j=size;j>0;j--){
// 這里要加上等于
if(j>=weight[i]){
dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
}else{
dp[j]=dp[j];
}
}
}
System.out.println(dp[size]);
}
/* public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int size = sc.nextInt();
int[] value = new int[M];
int[] weight = new int[M];
for(int i = 0; i < M;i++) {
weight[i] = sc.nextInt();
}
for(int i = 0; i < M;i++) {
value[i] = sc.nextInt();
}
int[][] dp = new int[weight.length][size+1];
for(int i=0;i<weight.length;i++){
dp[i][0]=0;
}
// 若比weight小則為0 若比weight大則為value
for(int i=0;i<=size;i++){
if(i<weight[0]){
dp[0][i]=0;
}else{
dp[0][i]=value[0];
}
}
for(int i=1;i<weight.length;i++){
for(int j=1;j<=size;j++){
// 這里要加上等于
if(j>=weight[i]){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
System.out.println(dp[weight.length-1][size]);
}*/
}
/*
// weight 空間，value代表價(jià)值，size 代表行李空間
public static int bagProblem(int[] weight,int[] value,int size){
//卡哥做法：
//1 確認(rèn)dp數(shù)組，以及dp數(shù)組下標(biāo)的含義
// dp數(shù)組 二維數(shù)組 dp[i][j]
// 下標(biāo)的含義 任意取物品0~i可存入空間為j的背包的最大值
//2 確定遞推公式
// 對(duì)于物品i 有兩種選擇 取兩者中的最大值
// 1 取物品i: 則當(dāng)前i j 的value 為 dp[i-1][j-weight[i]]+value[i]
// 2 不取物品i:則當(dāng)前 i j 的value 為dp[i-1][j];
// 若weight[i]>j 則沒法取第一種情況，直接取第二種情況
//3 dp數(shù)組如何初始化
// dp[i][j] 的值來自 dp[i-1][j] dp[i-1][j-weight[i]]
// 則第一列和第一行需要有值
// 第一列的值都為0 因?yàn)閖為0
// 第一行的值是物品0的值，當(dāng)weight<j時(shí) 都為0 當(dāng)weight>=j時(shí)都為物品0的weight
//4 確定遍歷順序
// 按行列都可以
//5 舉例推導(dǎo)dp數(shù)組
int[][] dp = new int[weight.length][size+1];
for(int i=0;i<weight.length;i++){
dp[i][0]=0;
}
// 若比weight小則為0 若比weight大則為value
for(int i=0;i<=size;i++){
if(i<weight[0]){
dp[0][i]=0;
}else{
dp[0][i]=value[0];
}
}
for(int i=1;i<weight.length;i++){
for(int j=1;j<=size;j++){
if(j>weight[i]){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[weight.length-1][size];
}
}*/
/*import java.util.*;
public class Main {
public static void main(String[] args) {
// 背包容量 N
// 物品種類 M
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int[] values = new int[M];
int[] weights = 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 = weights[0]; i <= N; i++) {
dp[0][i] = values[0];
}
// 先物品
for(int i = 1; i < M; i++) {
// 后背包
for(int j = 0; j <= N; j++) {
if(weights[i] > j) {
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]);
}
}*/分割等和子集
力扣題目鏈接(opens new window)
題目難易：中等
給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
注意: 每個(gè)數(shù)組中的元素不會(huì)超過 100 數(shù)組的大小不會(huì)超過 200
示例 1:
- 輸入: [1, 5, 11, 5]
- 輸出: true
- 解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].
示例?2:
- 輸入: [1, 2, 3, 5]
- 輸出: false
- 解釋: 數(shù)組不能分割成兩個(gè)元素和相等的子集.
看到題目的第一想法
? ? ? ?卡哥說可以用背包，但是我沒想到
看到代碼隨想錄之后的想法(二維數(shù)組)
? ? ? ? 其實(shí)題意就是這個(gè)數(shù)組能否拆分成總的sum的一半
? ? ? ? 若總和無法到達(dá)一半 ，則無法湊成
? ? ? ? 若總和可以拆分，題意為：0~i的物品填入sum/2的背包能否填滿
? ? ? ?1 dp數(shù)組的定義和下標(biāo)的含義
? ? ? ? dp[j] 物品0~i之間能填入背包j的最大價(jià)值
? ? ? ? 背包大小sum/2
? ? ? ? 2 確定遞推公式
? ? ? ? ?dp[j] =Math.max(dp[j],dp[j-weight[i]]+value[i]);?
? ? ? ? weight[i] 和 value[i] 都為nums[i]
??? ? ? 3 dp數(shù)組初始化
? ? ? ? ????????都為0
????????4 確定遍歷順序
? ? ? ? 先物品后背包
? ? ? ? 且從后往前
? ? ? ? 5 舉例推導(dǎo)dp數(shù)組
自己實(shí)現(xiàn)過程中遇到的困難(二維數(shù)組)
? ? ? ?1 確定dp[i][j]時(shí),若weight[i]>j 則沒法取第二種情況，直接取第一種情況dp[i-1][j]
? ? ? ? 2 行列需要確認(rèn)
? ? ? ? 3 看dp[sum/2] 是否==sum/2文章來源地址http://www.zghlxwxcb.cn/news/detail-802421.html
class Solution {
public boolean canPartition(int[] nums) {
//背包問題:背包存放的最大價(jià)值，看是否選中該物品，在目標(biāo)背包大小中取最大值
//該問題:背包存放的最大價(jià)值，在當(dāng)前背包大小為target時(shí)，看最大價(jià)值是否能填滿這個(gè)target
//兩個(gè)子集的元素和相等
//其實(shí)就是求整個(gè)數(shù)組的和的一半，看數(shù)組中的值能否達(dá)到
//轉(zhuǎn)換成背包問題，一個(gè)背包 大小為為nums總和的一半，如何相加才能填滿
//dp數(shù)組下標(biāo)的含義
//dp數(shù)組
//背包的重量 nums
//背包的價(jià)值 nums
//不可重復(fù)放入
// 確定dp數(shù)組的定義和每個(gè)下標(biāo)的含義
// dp[] 為0~i下標(biāo)填入背包空間j的最大價(jià)值,看是否等于11
// 確定遞推公式
// dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
// 確定遍歷順序
// 從后往前
// dp數(shù)組初始化
// 都為0
// 手動(dòng)推導(dǎo)dp數(shù)組
int sum = 0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
if(nums.length==1){
return false;
}
if(sum%2==1){
return false;
}
int target = sum/2;
int[] dp = new int[target+1];
//i為物品
//j為空間
for(int i=0;i<nums.length;i++){
for(int j=target;j>=nums[i];j--){
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
//若這個(gè)位置的dp[j]可以填滿
if(dp[j]==target){
return true;
}
}
}
return false;
}
}到了這里，關(guān)于動(dòng)態(tài)規(guī)劃day04（01背包問題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
