?一段時(shí)間沒寫文章钉凌，這兩天整了下有關(guān)完全背包的內(nèi)容肮疗，跟小伙伴們分享下。
一、問題描述
?在N種物品中選取若干件（同一種物品可多次選仍曰獭）放在空間為V的背包里，每種物品的體積為v1咱旱，v2更鲁，…，vn呵晨，與之相對(duì)應(yīng)的價(jià)值為w1,w2魏保，…，wn摸屠。求解怎么裝物品可使背包里物品不超過背包容量谓罗，且總價(jià)值最大。
二季二、基本思路
?這個(gè)問題非常類似于01背包問題妥衣，所不同的是每種物品有無限件。也就是從每種物品的角度考慮戒傻，與它相關(guān)的策略已并非取或不取兩種税手，而是有取0件、取1件需纳、取2件……等很多種芦倒。如果仍然按照解01背包時(shí)的思路，令f[i][V]表示前i種物品恰放入一個(gè)容量為V的背包的最大權(quán)值不翩，用k表示當(dāng)前容量下可以裝第i種物品的件數(shù)兵扬，那么k的范圍應(yīng)該是0≤k≤V/v[i]。同樣的口蝠，我們?nèi)匀豢梢园凑彰糠N物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程：
三器钟、基本算法
?代碼實(shí)現(xiàn)如下所示：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int N; //物品個(gè)數(shù)
int V; //背包容量
cout<<"輸入物品的個(gè)數(shù)及背包的容量:";
cin>>N>>V;
vector<int> v(N+1); //存儲(chǔ)物品的體積，第一個(gè)位置空出來
vector<int> w(N+1); //存儲(chǔ)物品的價(jià)值妙蔗，第一個(gè)位置空出來
vector<vector<int> > F(N+1,vector<int>(V+1)); //DP表傲霸，初始化數(shù)組默認(rèn)填充為0
for(int i=1;i<=N;i++){
cin>>v[i]>>w[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k * v[i] <= j; k++) {
/*如果能放下*/
if(v[i]<=j){
F[i][j]=max(F[i-1][j],F[i-1][j-k*v[i]]+k*w[i]);
/*要么不取，要么取0件眉反、取1件昙啄、取2件……取k件*/
}else{
/*放不下的話*/
F[i][j]=F[i-1][j];
/*繼承前i個(gè)物品在當(dāng)前空間大小時(shí)的價(jià)值*/
}
}
}
}
for(int i=0;i<=N;i++){
for(int j=0;j<=V;j++){
cout<<F[i][j]<<" ";
}
cout<<endl;
}
cout<<"最大價(jià)值是："<<F[N][V]<<endl;
return 0;
}
?程序運(yùn)行截圖：
四、算法優(yōu)化
?代碼如下：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int N; //物品個(gè)數(shù)
int V; //背包容量
cout<<"輸入物品的個(gè)數(shù)及背包的容量:";
cin>>N>>V;
vector<int> v(N+1); //存儲(chǔ)物品的體積寸五，第一個(gè)位置空出來
vector<int> w(N+1); //存儲(chǔ)物品的價(jià)值梳凛，第一個(gè)位置空出來
vector<vector<int> > F(N+1,vector<int>(V+1)); //DP表
for(int i=1;i<=N;i++){
cin>>v[i]>>w[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k * v[i] <= j; k++) {
/*如果能放下*/
if(v[i]<=j){
F[i][j]=max(F[i-1][j],F[i][j-v[i]]+w[i]);
/*要么不取，要么取0件梳杏、取1件韧拒、取2件……取k件*/
}else{
/*放不下的話*/
F[i][j]=F[i-1][j];
/*繼承前i個(gè)物品在當(dāng)前空間大小時(shí)的價(jià)值*/
}
}
}
}
for(int i=0;i<=N;i++){
for(int j=0;j<=V;j++){
cout<<F[i][j]<<" ";
}
cout<<endl;
}
cout<<"最大價(jià)值是："<<F[N][V]<<endl;
return 0;
}
?此時(shí)淹接，狀態(tài)和同層的i相關(guān)，狀態(tài)可以繼續(xù)壓縮叛溢，可以從小到大循環(huán)蹈集。
?所以對(duì)于
可以使用一維數(shù)組來簡(jiǎn)化表示為：
?代碼進(jìn)一步優(yōu)化，如下所示：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int N; //物品個(gè)數(shù)
int V; //背包容量
cout<<"輸入物品的個(gè)數(shù)及背包的容量:";
cin>>N>>V;
vector<int> v(N+1); //存儲(chǔ)物品的體積雇初，第一個(gè)位置空出來
vector<int> w(N+1); //存儲(chǔ)物品的價(jià)值拢肆，第一個(gè)位置空出來
vector<int> F(V+1); //DP表
for(int i=1;i<=N;i++){
cin>>v[i]>>w[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
/*如果能放下*/
if(v[i]<=j){
F[j]=max(F[j],F[j-v[i]]+w[i]);
/*要么不取，要么取0件靖诗、取1件郭怪、取2件……取k件*/
}else{
/*放不下的話*/
F[j]=F[j];
/*繼承前i個(gè)物品在當(dāng)前空間大小時(shí)的價(jià)值*/
}
}
}
for(int i=0;i<=V;i++){
cout<<F[i]<<" ";
}
cout<<endl;
cout<<"最大價(jià)值是："<<F[V]<<endl;
return 0;
}
?程序運(yùn)行截圖：
?才疏學(xué)淺，假若有錯(cuò)誤的地方刊橘，還請(qǐng)各位同道中人指點(diǎn)迷津鄙才。
