多重背包問題

1.多重背包問題

問題描述：有一個容積為V的背包，同時有N種物品,有對應種類的體積w和價值v，且每種物品K件；求該背包最多能裝下的物品價值總和。

分析問題：

将完全背包問題轉換為0-1背包問題，背包對每種物品能裝入min{k,V/wi}件，是以轉換為0-1背包問題則物品總數N為

狀态描述：dp[i][j]表示第i件物品對于目前占用容量為j的價值狀态，其中1<=i<=N,0<=j<=V;

狀态分析：第i件物品是否加入背包，

                （1）加入，dp[i][j]等于dp[i-1][j-w]+v，第i-1件相對于j-wi的占容最大價值的最大價值加第i件價值；

                  (2)   沒加入，d[i][j]等于dp[i-1][j],即與第i-1件到j占容的最大價值；

 狀态轉換：

轉換為一維：

轉換結果：dp[V],第N件物品到占容為V的最大價值狀态，即完全背包問題的最優價值總和。

時間複雜度分析：

測試資料集：

1

8 2

4 100 2

2 100 4

狀态矩陣：

0 0 0 100 100 100 100 100 

0 0 0 100 100 100 100 200 

0 100 100 100 100 200 200 200 

0 100 100 200 200 200 200 300 

0 100 100 200 200 300 300 300 

0 100 100 200 200 300 300 400 

Code(轉換為0-1) :

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int main(){
	int C;
	int V,N;
	struct goods{
		int w;
		int v;
	};
	vector<int> dp(101,0);
	vector<goods> goods(1,{0,0});//物品總數
	int w,v,k;
	cin>>C;
	while(C--){
		goods.erase(goods.begin()+1, goods.end());
		cin>>V>>N;
		int n=0;
		for(int i=1;i<=N;i++){
			cin>>w>>v>>k;
			n+=min(k,V/w);
			goods.insert(goods.end(), min(k,V/w), {w,v});
		}
		for(int j=0;j<=V;j++){
			dp[j]=0;
		}
		for(int i=1;i<=n;i++){//物品最大總數N
			for(int j=V;j>=goods[i].w;j--){//0-1，逆序
				dp[j]=max(dp[j],dp[j-goods[i].w]+goods[i].v);
			}
			for(int j=1;j<=V;j++)
				cout<<dp[j]<<" ";
			cout<<endl;
		}
		cout<<dp[V]<<endl;
	}
	return 0;
}
           

簡化0-1代碼：

struct goodsClass{
    int w;
    int v;
    int k;
}
for(int i=i;i<N;i++){//N為物品種類數
    for(int j=V;j>goodsClass[i].w;j--){//自右向左，自左向右都可，逆序便于了解0-1背包
        for(int k=1;k<goodsClass[i].k&&j>=k*goodsClass[i].w;k++){
            dp[j]=max(dp[j],dp[j-k*goodsClass[i].w]+k*goodsClass[i].v);
        }
    }
}//求多重背包

           

以上簡化時間複雜度為

，若想優化其複雜度可使用二進制拆分法轉換為以組為機關的0-1背包問題，其時間複雜度為

,或是借助單調隊列實作，其複雜度為

.

*擴充

基于上述0-1簡化代碼，可實作對完全背包問題求解：

for(int i=1;i<=N;i++){
    for(int j=V;j>=goodsClass[i].w;j--){
        for(int k=1;j>=k*goodsClass[i].w;k++){//j>=k*goodsClass[i].w確定dp不越界，同時保證1<=k<=V/goodsClass[i].w
            dp[j]=max(dp[j],dp[j-k*goodsClass[i].w]+k*goodsClass[i].v);
        }
    }
}
           

最後建議：求背包問題都轉換為0-1背包問題，若需要優化則再考慮優化。