背包问题---完全背包(最优方案总数分析及实现)

小程序880 更新时间：2025-06-08 09:09:47

2023年8月1日发(作者：)

背包问题----完全背包（最优⽅案总数分析及实现）本⼈博⽂》中已详细谈过完全背包问题，同时在博⽂》中也总结过01背包的最优⽅案总数的实现。这⾥我们模仿01背包最优⽅案总数⽅法给出完全背包的最优⽅案求解⽅法。

重写完全背包的动态规划的状态及状态⽅程：完全背包是在N种物品中选取若⼲件（同⼀种物品可多次选取）放在空间为V的背包⾥，每种物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解怎么装物品可使背包⾥物品总价值最⼤。

设物品种类为N，背包容量为V，每种物品的体积为C[i]，价值为W[i]。⼦问题定义：F[i][j]表⽰前i种物品中选取若⼲件物品放⼊剩余空间为j的背包中所能得到的最⼤价值。状态⽅程为： (2-2)

在⽂章》中曾定义G[i][j]代表F[i][j]的⽅案总数。这⾥我们也做相同的定义，那么最终的结果应该为G[N][V]。

由01背包转变到完全背包后G[i][j]该怎么求？对于01背包来说，G[i][j]求法如下（摘⾃：》）：如果F[i][j]=F[i-1][j]且F[i][j]!=F[i-1][j-C[i]]+W[i]说明在状态[i][j]时只有前i-1件物品的放⼊才会使价值最⼤，所以第i件物品不放⼊，那么到状态[i][j]的⽅案数应该等于[i-1][j]状态的⽅案数即G[i][j]=G[i-1][j]；如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]!=F[i-1][j]说明在状态[i][j]时只有第i件物品的加⼊才会使总价值最⼤，那么⽅案数应该等于[i-1][j-C[i]]的⽅案数，即G[i][j]=G[i-1][j-C[i]]；如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]=F[i-1][j]则说明即可以通过状态[i-1][j]在不加⼊第i件物品情况下到达状态[i][j]，⼜可以通过状态[i-1][j-C[i]]在加⼊第i件物品的情况下到达状态[i][j]，并且这两种情况都使得价值最⼤且这两种情况是互斥的，所以⽅案总数为G[i][j]=G[i-1][j-C[i]]+ G[i-1][j]。

对于完全背包，我们也可以根据其状态⽅程来进⾏条件判断：如果F[i][j] = F[i-1][j]且F[i][j] != F[i][j-C[i]]+W[i]，说明背包总不存在第i种物品，也就是说背包种物品仍由前i-1种物品组成，那么应该有G[i][j] = G[i-1][j]；如果F[i][j] = F[i][j-C[i]]+W[i]且F[i][j] != F[i-1][j]，则说明背包中必定存在第i种物品使背包达到[i][j]状态的最⼤值，G[i][j] = G[i][j-C[i]]；如果F[i][j] = F[i][j-C[i]]+W[i]且F[i][j] = F[i-1][j]，则说明背包中存在i与不存在i都可以达到最⼤值，那么这个⽅案数应该由两者叠加，因为这两种情况是互斥的，即G[i][j] = G[i-1][j]+G[i][j-C[i]]。伪代码如下（注意和01背包情况的区分）：[cpp]

01.

02.

03.

04.

05.

06.

07.

08.

09.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

F[0][] ← 0

F[][0] ← 0

G[][ ] ← 1

for i ← 1 to N

do for j ← 1 to V

F[i][j] ← F[i-1][j]

G[i][j] ← G[i-1][j]

if (j >= C[i])

if (F[i][j] < F[i][j-C[i]]+W[i])

then F[i][j] ← F[i][j-C[i]]+W[i]

G[i][j] ← G[i][j-C[i]]

else if (F[i][j] = F[i][j-C[i]]+W[i])

then G[i][j] ← G[i-1][j]+G[i][j-C[i]]

return F[N][V] and G[N][V]

同样，上述⽅法在保存状态F[][]及G[][]时需要O(NV)的空间复杂度，下⾯我们对空间复制度进⾏优化。压缩空间复杂度为O(V)F[i][j]与G[i][j]只分别与F[i-1][]和G[i-1][]的状态有关，所以我们可以⽤两个⼀维数组F[]和G[]来替换⼆维数组F[][]和G[][]。直接给出伪代码：[cpp]

01.

02.

03.

04.

05.

06.

07.

08.

09.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

F[] ← 0

G[] ← 1

for i ← 1 to N

do for j ← C[i] to V

if (F[j] < F[j-C[i]]+W[i])

then F[j] ← F[j-C[i]]+W[i]

G[j] ← G[j-C[i]]

else if (F[j] = F[j-C[i]]+W[i])

then G[j] ← G[j]+G[j-C[i]]

return F[V] and G[V]

和01背包的最优⽅案总数相⽐上述伪代码只是调换了⼀下C[i]与V的遍历顺序，具体思想请看博⽂

下⾯对数据表给出以上两种不同空间复杂度的详细代码：完全背包数据表（背包容量为10）物品号i体积C价值W因为完全背包的⽅案⼀般较多，这⾥只列举3种物品，⽅便⼤家验证。//时间复杂度O(VN),空间复杂度为O(VN)#include #include #define N 101using namespace std;int MaxValueTable[N][N],OptimalTable[N][N];int Package02Optimal(int Weight[], int Value[], int nLen, int nCapacity){125225325 //initiallize all OptimalTable[][] with 1 for(int i = 0; i <= nLen; i++) for(int j = 0; j <= nCapacity; j++) OptimalTable[i][j] = 1;

for(int i2 = 1; i2 <= nLen; i2++) { for(int j2 = 1; j2 <= nCapacity; j2++) { MaxValueTable[i2][j2] = MaxValueTable[i2-1][j2]; OptimalTable[i2][j2] = OptimalTable[i2-1][j2]; if(j2 >= Weight[i2-1]) { if(MaxValueTable[i2][j2] < MaxValueTable[i2][j2-Weight[i2-1]]+Value[i2-1]) { MaxValueTable[i2][j2] = MaxValueTable[i2][j2-Weight[i2-1]]+Value[i2-1]; OptimalTable[i2][j2] = OptimalTable[i2][j2-Weight[i2-1]]; } else if(MaxValueTable[i2][j2] == (MaxValueTable[i2][j2-Weight[i2-1]]+Value[i2-1])) { OptimalTable[i2][j2] = OptimalTable[i2-1][j2]+OptimalTable[i2][j2-Weight[i2-1]]; } } } } cout << endl << "OptimalCount:" << OptimalTable[nLen][nCapacity] << endl; int nRet = MaxValueTable[nLen][nCapacity]; return nRet;}int main()

{

//int Weight[] = {3,2,5,1,6,4};

//int Value[] = {6,5,10,2,16,8};

int Weight[] = {2,2,2};

int Value[] = {5,5,5};

int nCapacity = 10;

cout << "MaxValue:" << Package02Optimal(Weight,Value,sizeof(Weight)/sizeof(int),nCapacity) << endl;

// cout << "MaxValue:" << Package02Optimal_Compress(Weight,Value,sizeof(Weight)/sizeof(int),nCapacity) << endl;

return 0;

}

//时间复杂度O(VN),空间复杂度为O(V)#includeusing namespace std;#define Size 1111int dp[Size];int OptimalTable[Size];int Max(int x,int y){ return x>y?x:y;}int Package01_Compress(int Weight[], int Value[], int goodsN, int maxWeight){ int i,j; /*======初始化======*/ memset(dp,0,sizeof(dp)); for(int kt=0;kt<=maxWeight;kt++) OptimalTable[kt]=1; /*======初始化======*/ for(i=1;i<=goodsN;i++) //即怎么都有⼀种 for(j=Weight[i];j<=maxWeight;j++){

if(dp[j]<(dp[j-Weight[i]]+Value[i])){//说明选第i最优 dp[j] = dp[j-Weight[i]]+Value[i]; OptimalTable[j]=OptimalTable[j-Weight[i]];//⽅案数和[j-Weight[i]]⼀样 } else if(dp[j]==(dp[j-Weight[i]]+Value[i])){ OptimalTable[j] = OptimalTable[j-Weight[i]]+OptimalTable[j]; }

} return dp[maxWeight];

}int main(){ int va[Size],vm[Size];

int t,n,m; int i; cin>>t; //t组测试数据 while(t--) { cin>>n>>m; //n为个数,m为最⼤载重量 for(i=1;i<=n;i++) cin>>va[i]; for(i=1;i<=n;i++) cin>>vm[i]; int myWhats=Package01_Compress(vm,va, n, m); cout<

2023年8月1日发(作者：)

背包问题----完全背包（最优⽅案总数分析及实现）本⼈博⽂》中已详细谈过完全背包问题，同时在博⽂》中也总结过01背包的最优⽅案总数的实现。这⾥我们模仿01背包最优⽅案总数⽅法给出完全背包的最优⽅案求解⽅法。

重写完全背包的动态规划的状态及状态⽅程：完全背包是在N种物品中选取若⼲件（同⼀种物品可多次选取）放在空间为V的背包⾥，每种物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解怎么装物品可使背包⾥物品总价值最⼤。

设物品种类为N，背包容量为V，每种物品的体积为C[i]，价值为W[i]。⼦问题定义：F[i][j]表⽰前i种物品中选取若⼲件物品放⼊剩余空间为j的背包中所能得到的最⼤价值。状态⽅程为： (2-2)

在⽂章》中曾定义G[i][j]代表F[i][j]的⽅案总数。这⾥我们也做相同的定义，那么最终的结果应该为G[N][V]。

由01背包转变到完全背包后G[i][j]该怎么求？对于01背包来说，G[i][j]求法如下（摘⾃：》）：如果F[i][j]=F[i-1][j]且F[i][j]!=F[i-1][j-C[i]]+W[i]说明在状态[i][j]时只有前i-1件物品的放⼊才会使价值最⼤，所以第i件物品不放⼊，那么到状态[i][j]的⽅案数应该等于[i-1][j]状态的⽅案数即G[i][j]=G[i-1][j]；如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]!=F[i-1][j]说明在状态[i][j]时只有第i件物品的加⼊才会使总价值最⼤，那么⽅案数应该等于[i-1][j-C[i]]的⽅案数，即G[i][j]=G[i-1][j-C[i]]；如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]=F[i-1][j]则说明即可以通过状态[i-1][j]在不加⼊第i件物品情况下到达状态[i][j]，⼜可以通过状态[i-1][j-C[i]]在加⼊第i件物品的情况下到达状态[i][j]，并且这两种情况都使得价值最⼤且这两种情况是互斥的，所以⽅案总数为G[i][j]=G[i-1][j-C[i]]+ G[i-1][j]。

对于完全背包，我们也可以根据其状态⽅程来进⾏条件判断：如果F[i][j] = F[i-1][j]且F[i][j] != F[i][j-C[i]]+W[i]，说明背包总不存在第i种物品，也就是说背包种物品仍由前i-1种物品组成，那么应该有G[i][j] = G[i-1][j]；如果F[i][j] = F[i][j-C[i]]+W[i]且F[i][j] != F[i-1][j]，则说明背包中必定存在第i种物品使背包达到[i][j]状态的最⼤值，G[i][j] = G[i][j-C[i]]；如果F[i][j] = F[i][j-C[i]]+W[i]且F[i][j] = F[i-1][j]，则说明背包中存在i与不存在i都可以达到最⼤值，那么这个⽅案数应该由两者叠加，因为这两种情况是互斥的，即G[i][j] = G[i-1][j]+G[i][j-C[i]]。伪代码如下（注意和01背包情况的区分）：[cpp]

01.

02.

03.

04.

05.

06.

07.

08.

09.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

F[0][] ← 0

F[][0] ← 0

G[][ ] ← 1

for i ← 1 to N

do for j ← 1 to V

F[i][j] ← F[i-1][j]

G[i][j] ← G[i-1][j]

if (j >= C[i])

if (F[i][j] < F[i][j-C[i]]+W[i])

then F[i][j] ← F[i][j-C[i]]+W[i]

G[i][j] ← G[i][j-C[i]]

else if (F[i][j] = F[i][j-C[i]]+W[i])

then G[i][j] ← G[i-1][j]+G[i][j-C[i]]

return F[N][V] and G[N][V]

同样，上述⽅法在保存状态F[][]及G[][]时需要O(NV)的空间复杂度，下⾯我们对空间复制度进⾏优化。压缩空间复杂度为O(V)F[i][j]与G[i][j]只分别与F[i-1][]和G[i-1][]的状态有关，所以我们可以⽤两个⼀维数组F[]和G[]来替换⼆维数组F[][]和G[][]。直接给出伪代码：[cpp]

01.

02.

03.

04.

05.

06.

07.

08.

09.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

F[] ← 0

G[] ← 1

for i ← 1 to N

do for j ← C[i] to V

if (F[j] < F[j-C[i]]+W[i])

then F[j] ← F[j-C[i]]+W[i]

G[j] ← G[j-C[i]]

else if (F[j] = F[j-C[i]]+W[i])

then G[j] ← G[j]+G[j-C[i]]

return F[V] and G[V]

和01背包的最优⽅案总数相⽐上述伪代码只是调换了⼀下C[i]与V的遍历顺序，具体思想请看博⽂

下⾯对数据表给出以上两种不同空间复杂度的详细代码：完全背包数据表（背包容量为10）物品号i体积C价值W因为完全背包的⽅案⼀般较多，这⾥只列举3种物品，⽅便⼤家验证。//时间复杂度O(VN),空间复杂度为O(VN)#include #include #define N 101using namespace std;int MaxValueTable[N][N],OptimalTable[N][N];int Package02Optimal(int Weight[], int Value[], int nLen, int nCapacity){125225325 //initiallize all OptimalTable[][] with 1 for(int i = 0; i <= nLen; i++) for(int j = 0; j <= nCapacity; j++) OptimalTable[i][j] = 1;

for(int i2 = 1; i2 <= nLen; i2++) { for(int j2 = 1; j2 <= nCapacity; j2++) { MaxValueTable[i2][j2] = MaxValueTable[i2-1][j2]; OptimalTable[i2][j2] = OptimalTable[i2-1][j2]; if(j2 >= Weight[i2-1]) { if(MaxValueTable[i2][j2] < MaxValueTable[i2][j2-Weight[i2-1]]+Value[i2-1]) { MaxValueTable[i2][j2] = MaxValueTable[i2][j2-Weight[i2-1]]+Value[i2-1]; OptimalTable[i2][j2] = OptimalTable[i2][j2-Weight[i2-1]]; } else if(MaxValueTable[i2][j2] == (MaxValueTable[i2][j2-Weight[i2-1]]+Value[i2-1])) { OptimalTable[i2][j2] = OptimalTable[i2-1][j2]+OptimalTable[i2][j2-Weight[i2-1]]; } } } } cout << endl << "OptimalCount:" << OptimalTable[nLen][nCapacity] << endl; int nRet = MaxValueTable[nLen][nCapacity]; return nRet;}int main()

{

//int Weight[] = {3,2,5,1,6,4};

//int Value[] = {6,5,10,2,16,8};

int Weight[] = {2,2,2};

int Value[] = {5,5,5};

int nCapacity = 10;

cout << "MaxValue:" << Package02Optimal(Weight,Value,sizeof(Weight)/sizeof(int),nCapacity) << endl;

// cout << "MaxValue:" << Package02Optimal_Compress(Weight,Value,sizeof(Weight)/sizeof(int),nCapacity) << endl;

return 0;

}

//时间复杂度O(VN),空间复杂度为O(V)#includeusing namespace std;#define Size 1111int dp[Size];int OptimalTable[Size];int Max(int x,int y){ return x>y?x:y;}int Package01_Compress(int Weight[], int Value[], int goodsN, int maxWeight){ int i,j; /*======初始化======*/ memset(dp,0,sizeof(dp)); for(int kt=0;kt<=maxWeight;kt++) OptimalTable[kt]=1; /*======初始化======*/ for(i=1;i<=goodsN;i++) //即怎么都有⼀种 for(j=Weight[i];j<=maxWeight;j++){

if(dp[j]<(dp[j-Weight[i]]+Value[i])){//说明选第i最优 dp[j] = dp[j-Weight[i]]+Value[i]; OptimalTable[j]=OptimalTable[j-Weight[i]];//⽅案数和[j-Weight[i]]⼀样 } else if(dp[j]==(dp[j-Weight[i]]+Value[i])){ OptimalTable[j] = OptimalTable[j-Weight[i]]+OptimalTable[j]; }

} return dp[maxWeight];

}int main(){ int va[Size],vm[Size];

int t,n,m; int i; cin>>t; //t组测试数据 while(t--) { cin>>n>>m; //n为个数,m为最⼤载重量 for(i=1;i<=n;i++) cin>>va[i]; for(i=1;i<=n;i++) cin>>vm[i]; int myWhats=Package01_Compress(vm,va, n, m); cout<

本文发布于:2023-08-01，感谢您对本站的认可！

本文链接:http://torson.com.cn/chengxu/1690820772a436638.html