💬推薦一款模拟面試、刷題神器，從基礎到大廠面試題👉點選跳轉刷題網站進行注冊學習
文章目錄
- 前言
- 一、什麼是多重背包？
- 二、二進制拆分
- 三、例題及代碼實作
- 總結
前言
背包問題分為：01背包，完全背包以及多重背包，本文主要講解多重背包。
01背包以及01背包的優化講解：
01背包：https://blog.csdn.net/m0_55486529/article/details/123806820
01背包優化：https://blog.csdn.net/m0_55486529/article/details/123831655
完全背包：https://blog.csdn.net/m0_55486529/article/details/123854386
提示：以下是本篇文章正文内容，下面案例可供參考
一、什麼是多重背包？
給定n種物品，每種物品都有重量w,和價值v;，第i種物品有c;個。背包容量為W，求解在不超過背包容量的情況下如何放置物品，使背包中物品的價值之和最大。
首先，01背包是指物品的個數為一，完全背包是物品的個數沒有限制（無窮多），多重背包就是完全背包和01背包的組合，當物品個數c[ i ] * 重量w [ i ] >= 背包容量 j時，相當于完全背包，當 c[ i ]*w[ i ]<j 時我們可以轉化為01背包解決問題。
可以通過暴力拆分或二進制拆分将多重背包問題轉化為01背包問題，也可以通過數組優化解決可行性問題。
其中，完全背包就像完全背包一樣解決（上面有連結，可以學習完全背包）
最難的就是怎麼轉化為01背包，這裡我們使用二進制拆分。
二、二進制拆分
其實二進制拆分，我們可以把它了解成将c[i]個物品打包分成 幾份，相當于把100個蘋果分成好幾箱，每一箱的個數是2的幾次方，最後如果不夠就把剩下的放一箱。
三、例題及代碼實作
代碼如下：
public class test {
public static void main(String[] args) {
// TODO 自動生成的方法存根
int[] w= {2,5,4,2,3}; //單個物品重量
int[] v= {6,3,5,4,6}; //單個物品價值
int[] c= {2,2,5,5,4}; //物品個數
System.out.println(bagkiller(c,w,v,10));
}
public static int bagkiller(int[] c,int[] w,int[] v,int n) {
int [] dp=new int[n+1];
for (int i=0;i<w.length;i++) {
if (c[i]*w[i]>=n) { //如果物品個數c[ i ] * 重量w [ i ] >= 背包容量 j時，相當于完全背包
for (int j=w[i];j<=n;j++) { //轉化為完全背包
dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);
}
}else {
for (int k=1;c[i]>0;k<<=1) { //二進制拆分
int x=Math.min(c[i], k); //判斷剩餘的個數是否足夠二進制拆分
for (int j=n;j>=w[i];j--) { //轉化為01背包
dp[j]=Math.max(dp[j],dp[j-w[i]*x]+v[i]*x);
}
c[i]-=x;
}
}
}
return dp[n];
}
}
結果：
總結
以上就是今天要講的内容，本文僅僅簡單介紹了完全背包的概念，以及常用解決方法，以及二進制拆分的基本知識。