背包,物品物品,归纳,1种求解分组0
更新时间：2024-04-03
点赞:4799
浏览:14711
作者：用户投稿
本站原创
摘 要 探讨了分组0-1背包理由，了动态规划解决策略教学论文，在物品总数为n个和背包承重量为W时，递推的复杂度为O(nW)，回溯的复杂度为O(n).计算实例该策略教学论文易于找到最优解.
词 背包理由;NP完全;动态规划
中图分类号 TP301 文献标识码 A
A Dynamic Programming Method for
Classified 0-1 Knapsack Problem
JIANG Ya-jun1, YI Xue-jun2
(1.Department of Computer and Communication Engineering, Hunan University of Science and Engineering, Yongzhou，
Hunan 425100 China; 2.College of Mathematics and Econometrics, Hunan University, Changsha,Hunan 410082 China)
Abstract This paper studied the classified 0-1 knapsack problem, and proposed a dynamic programming method. The complexity of the recursive process is O(nW), and the complexity of the traceback process is O(n), where n is the total number of goods and W is the bearing weight of the knapsack. The example shows that it is easy to find the optimal solution by the method.
Key words Knapsack Problem; NP-complete; Dynamic Programming
1 引 言
0-1背包理由属于NP完全理由，表述为：已知n个物品和承重量为W的背包，每个物品i的重量为wi，价值为vi（i=1,2,…,n），现要以这n个物品中选出若干件放入背包，使得装入背包物品的总重量不超过W，且总价值达到最大.0-1背包理由在信息安全、工程决策等领域中极为的运用［1-5］,对0-1背包理由扩展探讨，如0-1二次背包理由［6］、多0-1背包理由［7］、多维0-1背包理由［8］等，十分的运用价值和学术作用小学数学教学论文.
将传统的0-1背包理由扩展为分组0-1背包理由，阐述了分组0-1背包理由的动态规划解决案例，为背包理由的运用拓展了新的思路.
2 分组0-1背包理由的数学模型
在分组0-1背包理由中，物品被分成若干组，在装入固定承重量的背包时，要求每组物品全部取完并且总价值最大.在选择装入背包的物品时，对每个物品两种选择，即装入背包或不装入背包.将物品装入背包多次，也只装入的物品.在这里假设物品的重量和背包的承重量正整数.分组0-1背包理由的数学模型描述为：
给定n个物品，分成r组，设为
{G11,…,G1s1,…,Gj1,…,Gjsj,…,Gr1,…,Grsr},
∑rj=1sj=n，r＞1，sj＞1（j=1,2,…,r）.各物品的重量和价值为：
{w11,…,w1s1,…,wj1,…,wjsj,…,wr1,…,wrsr},
{v11,…,v1s1,…,vj1,…,vjsj,…,vr1,…,vrsr},
wji＞0，vji＞0，i=1,…,sj，j=1,…,r.给定W＞0，求解n元0-1向量=(x11,…,x1s1,…,xj1,…,xjsj,…,xr1,…,xrsr)，使得当∑rj=1∑sji=1xjiwji≤W，∑sji=1xji＜sj时，∑rj=1∑sji=1xjivji达到最大.
3 动态规划法
为了用动态规划法求解分组0-1背包理由，用动态规划表M跟踪递推，行对应于每物品，列对应于背包的承重量， M(j)［i,k］代表第∑j－1l=1sl+i行第k列单元格的值，它表示当背包承重量为k时，以物品G11,…,G1s1,…,Gj1,…,Gji中选取但各组不建全部取完装入到背包最大价值.表格的填充以上到下，以左到右.
定理1 当0≤k≤W, 0≤i≤sj，1≤j≤r时，设M(1)［0,k］=0，M(j)［i,0］=0；当2≤j≤r时，设M(j)［0,k］=M(j－1)［sj－1,k］，则分组0-1背包理由中最优子集的最大价值递推公式为：
1）若1≤i＜sj，则
经 济 数 学第 29卷第1期蒋亚军等：求解分组0-1背包理由的动态规划法
M(j)［i,k］=M(j)［i－1,k］,k＜wji,max {M(j)［i－1,k］,M(j)［i－1,k－wji］+vji}，k≥wji.(1）
2）若i=sj，则
M(j)［sj,k］=
M(j)［sj－1,k］,k＜wjsj,max {M(j)［l－1,k－∑sjτ=l+1wjτ］+∑sjτ=l+1vjτ,l=1,2,…,sj},k≥∑sji=1wji,max {M(j)［sj－1,k］,M(j)［sj－1,k－wjsj］+vjsj},wjsj≤k＜∑sji=1wji.（2）
证明 对于有序物品组{G11,…,G1s1,…,Gj1,…,Gjsj,…,Gr1,…,Grsr}中第l个物品，有着(i,j)，使得l=s1+…+sj－1+i,这里1≤i≤sj，1≤j≤r.显然当1≤l≤s1时，即j=1时，令l=i.这里，当某组物品时，显然该组不作考虑，故这里假设sj＞1，j=1,2,…,r.
下面用归纳法来证明由递推公式给出的M(j)［i,k］相应的最大价值：
1）当l=1时(对应(i,j)=(1,1))，易知对于任意k，由公式（1）给出的M(1)［1,k］最大价值.
当l=2时(对应(i,j)=(2,1))，易知对于任意k，由公式（1）或公式(2) 给出的M(1)［2,k］最大价值.
2）假设1≤l≤m时（对应(i,j)），对于任意k，由公式（1）或公式(2) 给出的M(j)［i,k］最大价值.
3）下面证明对于l=m+1时（对应i′,j′），对于任意k，由公式（1）或公式（2）给出的M(j′)［i′,k］也最大价值.
分三种情形讨论：
（ⅰ）m=s1+…+sj′－1+i′－1（这里1≤i′＜sj′）,
1[3]
（ⅱ）m=s1+…+sj′－2+sj′－1,
（ⅲ）m=s1+…+sj′－1+sj′－1.
1）对于情形（ⅰ）， 当l=m+1时（对应i′,j′=i+1,j），i′＜sj′，第m+1个物品所在组，则该物品被取与否，该组都不会出现选满的情形.
当k＜wj′i′时，则第m+1个物品被取，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，M(j′)［i′,k］=M(j′)［i′－1,k］.
当k≥wj′i′时，则第m+1个物品有可能被取或不取两种情形：当第m+1个物品不取时，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k］；而当第m+1个物品被取时，由归纳假设M(j′)［i′－1,k－wj′i′］=M(j)［i,k－wj′i′］最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k－wj′i′］+vj′i′.综合前述两种情形有：M(j′)［i′,k］=max {M(j′)［i′－1,k］,M(j)［i′－1,k－wj′i′］+vj′i′}.
由上可知，当l=m+1（对应i′,j′），且m=s1+…+sj′－1+i′－1时（这里1≤i′＜sj′）, 有
M(j′)［i′,k］=
M(j′)［i′－1,k］,k＜wj′i′max {M(j′)［i′－1,k］,k≥wj′i′M(j)［i′－1,k－wj′i′］+vj′i′}
2）对于情形（ⅱ），当l=m+1（对应(i′,j′)=(1,j+1)），sj′＞1，第m+1个物品是所在组第1个，则该物品被取与否，该组都不会被全部选满.
当k＜wj′1时，则第j′类中第1个物品被选择，由归纳假设M(j′)［1,k］=M(j′－1)［sj′－1,k］=M(j′)［0,k］.
当k≥w(j′)1时，则第j′类中第1个物品有可能被取或不取两种情形：当第1个物品不取时，由题设及归纳假设M(j′)［0,k］=M(j′－1)［sj′－1,k］最大价值，所以M(j′)［1,k］=M(j′－1)［sj′－1,k］；而当第1个物品被取时， 由题设及归纳假设M(j′)［0,k－wj′1］=M(j′－1)［sj′－1,k－wj′1］最大价值，所以M(j′)［1,k］=M(j′)［0,k－wj′1］+vj′1.综合前述两种情形有：M(j′)［1,k］=max {M(j′)［0,k］,M(j′)［0,k－w(j′)1］+v(j′)1}.
由上可知，当l=m+1（对应(i′,j′)，且m=s1+…+sj′－2+sj′－1时，有
M(j′)［1,k］=M(j′)［0,k］,k＜wj′1;max {M(j′)［0,k］,
M(j′)［0,k－wj′1］+vj′1},k≥wj′1.
3）对于情形（ⅲ），当l=m+1时（对应(i′,j′)=(sj′,j′)=(i+1,j)），这里i=sj－1，第m+1个物品是所在组1个.
当k＜wj′sj′时，则第m+1个物品被选择，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k］.
当k≥∑sj′i=1wj′i时, 有sj′种情形：即当l=1,2,…,sj′时，第j′组中第l个物品不取,而的物品都取.由归纳假设M(j′)［l－1,k－∑sj′l=l+1wj′l］最大价值，所以
M(j′)［sj′,k］=max {M(j′)［l－1,k－∑sj′τ=l+1wj′τ］
+∑sj′τ=l+1vj′τ,l=1,2,…,sj′}.
当wj′sj′≤k＜∑sj′i=1wj′i时, 此时第m+1个物品有可能被取或不取两种情形:当第m+1个物品不取时，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，所以M(j′)［i′,k］=M(j′)［sj′,k］=M(j′)［i′－1,k］=M(j′)［sj′－1,k］；而当第m+1个物品被取时，由归纳假设M(j′)［sj′-1,k-wj′sj′］最大价值，所以M(j′)［sj′,k］=M(j′)［sj′-1,k-wj′sj′］+v(j′)sj′.综合前述两种情形有
M(j′)［sj,k］=max{M(j′)［sj′-1,k］,
M(j′)［sj,j′-1,k-wj′sj′］+vj′sj′}.
由式（1）、式（2）和式（3）可知，当l=m+1（对应i′,j′），且m=s1+…+sj′－1+sj′－1 时，有
M(j′)［sj′,k］=
M(j′)［sj′－1,k］,k＜wjsj′,max {M(j′)［l－1,k－∑sj′τ=l+1wj′τ］+∑sj′τ=l+1vj′τ,l=1,2,…,sj},k≥∑sj′i=1wj′i,max {M(j′)［sj′－1,k］,M(j′)［s(j′)－1,k－wj′sj′］+vj′sj′},wj′sj′≤k＜∑sji=1wj′i.
由1）、2）和3）可知，对于（ⅰ）、（ⅱ）和（ⅲ）三种情形证明了对于l=m+1（对应(i′,j′)），由递推公式（1）或（2）给出的M(j′)［i′,k］最大价值要求.
对于任意1≤l≤n（对应的(i,)）和任意k，由递推公式（1）或（2）给出的M(j)［i,k］为对应的最大价值.证毕.
为了动态规划表M求取最优子集，定义回溯表F来跟踪上述递推，行对应于每物品，列对应于背包的承重量.令
F(j)［i,k］=
0,M(j)［i,k］=M(j)［i－1,k－wji］+vji;sj－t,M(j)［sj,k］=M(j)［t,k－∑sjτ=t+2wjτ)］+∑sjτ=t+2vjτ, t=0,1,…,sj－2;1M(j)［i,k］=M(j)［i－1,k］.（3）
回溯以动态规划表M的M(r)［sr,T′］直到M(1)［0,0］，回溯策略教学论文描述为：
1）若F(j)［i,k］=0，则回溯至M(j)［i－1,k－wji］，此时令xji=1；
2）若F(j)［i,k］=1，则回溯至M(j)［i－1,k］，此时令xji=0；
3）若F(j)［i,k］=sj－t＞1，则回溯至M(j)［i－(sj－t),k－∑sjτ=t+2wjτ)］，此时令xjt+2=xjt+3=…=xjsj=1，xjt+1=0.
2[3]
词 背包理由;NP完全;动态规划
中图分类号 TP301 文献标识码 A
A Dynamic Programming Method for
Classified 0-1 Knapsack Problem
JIANG Ya-jun1, YI Xue-jun2
(1.Department of Computer and Communication Engineering, Hunan University of Science and Engineering, Yongzhou，
Hunan 425100 China; 2.College of Mathematics and Econometrics, Hunan University, Changsha,Hunan 410082 China)
Abstract This paper studied the classified 0-1 knapsack problem, and proposed a dynamic programming method. The complexity of the recursive process is O(nW), and the complexity of the traceback process is O(n), where n is the total number of goods and W is the bearing weight of the knapsack. The example shows that it is easy to find the optimal solution by the method.
Key words Knapsack Problem; NP-complete; Dynamic Programming
1 引 言
0-1背包理由属于NP完全理由，表述为：已知n个物品和承重量为W的背包，每个物品i的重量为wi，价值为vi（i=1,2,…,n），现要以这n个物品中选出若干件放入背包，使得装入背包物品的总重量不超过W，且总价值达到最大.0-1背包理由在信息安全、工程决策等领域中极为的运用［1-5］,对0-1背包理由扩展探讨，如0-1二次背包理由［6］、多0-1背包理由［7］、多维0-1背包理由［8］等，十分的运用价值和学术作用小学数学教学论文.
将传统的0-1背包理由扩展为分组0-1背包理由，阐述了分组0-1背包理由的动态规划解决案例，为背包理由的运用拓展了新的思路.
2 分组0-1背包理由的数学模型
在分组0-1背包理由中，物品被分成若干组，在装入固定承重量的背包时，要求每组物品全部取完并且总价值最大.在选择装入背包的物品时，对每个物品两种选择，即装入背包或不装入背包.将物品装入背包多次，也只装入的物品.在这里假设物品的重量和背包的承重量正整数.分组0-1背包理由的数学模型描述为：
给定n个物品，分成r组，设为
{G11,…,G1s1,…,Gj1,…,Gjsj,…,Gr1,…,Grsr},
∑rj=1sj=n，r＞1，sj＞1（j=1,2,…,r）.各物品的重量和价值为：
{w11,…,w1s1,…,wj1,…,wjsj,…,wr1,…,wrsr},
{v11,…,v1s1,…,vj1,…,vjsj,…,vr1,…,vrsr},
wji＞0，vji＞0，i=1,…,sj，j=1,…,r.给定W＞0，求解n元0-1向量=(x11,…,x1s1,…,xj1,…,xjsj,…,xr1,…,xrsr)，使得当∑rj=1∑sji=1xjiwji≤W，∑sji=1xji＜sj时，∑rj=1∑sji=1xjivji达到最大.
3 动态规划法
为了用动态规划法求解分组0-1背包理由，用动态规划表M跟踪递推，行对应于每物品，列对应于背包的承重量， M(j)［i,k］代表第∑j－1l=1sl+i行第k列单元格的值，它表示当背包承重量为k时，以物品G11,…,G1s1,…,Gj1,…,Gji中选取但各组不建全部取完装入到背包最大价值.表格的填充以上到下，以左到右.
定理1 当0≤k≤W, 0≤i≤sj，1≤j≤r时，设M(1)［0,k］=0，M(j)［i,0］=0；当2≤j≤r时，设M(j)［0,k］=M(j－1)［sj－1,k］，则分组0-1背包理由中最优子集的最大价值递推公式为：
1）若1≤i＜sj，则
经 济 数 学第 29卷第1期蒋亚军等：求解分组0-1背包理由的动态规划法
M(j)［i,k］=M(j)［i－1,k］,k＜wji,max {M(j)［i－1,k］,M(j)［i－1,k－wji］+vji}，k≥wji.(1）
2）若i=sj，则
M(j)［sj,k］=
M(j)［sj－1,k］,k＜wjsj,max {M(j)［l－1,k－∑sjτ=l+1wjτ］+∑sjτ=l+1vjτ,l=1,2,…,sj},k≥∑sji=1wji,max {M(j)［sj－1,k］,M(j)［sj－1,k－wjsj］+vjsj},wjsj≤k＜∑sji=1wji.（2）
证明 对于有序物品组{G11,…,G1s1,…,Gj1,…,Gjsj,…,Gr1,…,Grsr}中第l个物品，有着(i,j)，使得l=s1+…+sj－1+i,这里1≤i≤sj，1≤j≤r.显然当1≤l≤s1时，即j=1时，令l=i.这里，当某组物品时，显然该组不作考虑，故这里假设sj＞1，j=1,2,…,r.
下面用归纳法来证明由递推公式给出的M(j)［i,k］相应的最大价值：
1）当l=1时(对应(i,j)=(1,1))，易知对于任意k，由公式（1）给出的M(1)［1,k］最大价值.
当l=2时(对应(i,j)=(2,1))，易知对于任意k，由公式（1）或公式(2) 给出的M(1)［2,k］最大价值.
2）假设1≤l≤m时（对应(i,j)），对于任意k，由公式（1）或公式(2) 给出的M(j)［i,k］最大价值.
3）下面证明对于l=m+1时（对应i′,j′），对于任意k，由公式（1）或公式（2）给出的M(j′)［i′,k］也最大价值.
分三种情形讨论：
（ⅰ）m=s1+…+sj′－1+i′－1（这里1≤i′＜sj′）,
1[3]
（ⅱ）m=s1+…+sj′－2+sj′－1,
（ⅲ）m=s1+…+sj′－1+sj′－1.
1）对于情形（ⅰ）， 当l=m+1时（对应i′,j′=i+1,j），i′＜sj′，第m+1个物品所在组，则该物品被取与否，该组都不会出现选满的情形.
当k＜wj′i′时，则第m+1个物品被取，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，M(j′)［i′,k］=M(j′)［i′－1,k］.
当k≥wj′i′时，则第m+1个物品有可能被取或不取两种情形：当第m+1个物品不取时，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k］；而当第m+1个物品被取时，由归纳假设M(j′)［i′－1,k－wj′i′］=M(j)［i,k－wj′i′］最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k－wj′i′］+vj′i′.综合前述两种情形有：M(j′)［i′,k］=max {M(j′)［i′－1,k］,M(j)［i′－1,k－wj′i′］+vj′i′}.
由上可知，当l=m+1（对应i′,j′），且m=s1+…+sj′－1+i′－1时（这里1≤i′＜sj′）, 有
M(j′)［i′,k］=
M(j′)［i′－1,k］,k＜wj′i′max {M(j′)［i′－1,k］,k≥wj′i′M(j)［i′－1,k－wj′i′］+vj′i′}
2）对于情形（ⅱ），当l=m+1（对应(i′,j′)=(1,j+1)），sj′＞1，第m+1个物品是所在组第1个，则该物品被取与否，该组都不会被全部选满.
当k＜wj′1时，则第j′类中第1个物品被选择，由归纳假设M(j′)［1,k］=M(j′－1)［sj′－1,k］=M(j′)［0,k］.
当k≥w(j′)1时，则第j′类中第1个物品有可能被取或不取两种情形：当第1个物品不取时，由题设及归纳假设M(j′)［0,k］=M(j′－1)［sj′－1,k］最大价值，所以M(j′)［1,k］=M(j′－1)［sj′－1,k］；而当第1个物品被取时， 由题设及归纳假设M(j′)［0,k－wj′1］=M(j′－1)［sj′－1,k－wj′1］最大价值，所以M(j′)［1,k］=M(j′)［0,k－wj′1］+vj′1.综合前述两种情形有：M(j′)［1,k］=max {M(j′)［0,k］,M(j′)［0,k－w(j′)1］+v(j′)1}.
由上可知，当l=m+1（对应(i′,j′)，且m=s1+…+sj′－2+sj′－1时，有
M(j′)［1,k］=M(j′)［0,k］,k＜wj′1;max {M(j′)［0,k］,
M(j′)［0,k－wj′1］+vj′1},k≥wj′1.
3）对于情形（ⅲ），当l=m+1时（对应(i′,j′)=(sj′,j′)=(i+1,j)），这里i=sj－1，第m+1个物品是所在组1个.
当k＜wj′sj′时，则第m+1个物品被选择，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k］.
当k≥∑sj′i=1wj′i时, 有sj′种情形：即当l=1,2,…,sj′时，第j′组中第l个物品不取,而的物品都取.由归纳假设M(j′)［l－1,k－∑sj′l=l+1wj′l］最大价值，所以
M(j′)［sj′,k］=max {M(j′)［l－1,k－∑sj′τ=l+1wj′τ］
+∑sj′τ=l+1vj′τ,l=1,2,…,sj′}.
当wj′sj′≤k＜∑sj′i=1wj′i时, 此时第m+1个物品有可能被取或不取两种情形:当第m+1个物品不取时，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］最大价值，所以M(j′)［i′,k］=M(j′)［sj′,k］=M(j′)［i′－1,k］=M(j′)［sj′－1,k］；而当第m+1个物品被取时，由归纳假设M(j′)［sj′-1,k-wj′sj′］最大价值，所以M(j′)［sj′,k］=M(j′)［sj′-1,k-wj′sj′］+v(j′)sj′.综合前述两种情形有
M(j′)［sj,k］=max{M(j′)［sj′-1,k］,
M(j′)［sj,j′-1,k-wj′sj′］+vj′sj′}.
由式（1）、式（2）和式（3）可知，当l=m+1（对应i′,j′），且m=s1+…+sj′－1+sj′－1 时，有
M(j′)［sj′,k］=
M(j′)［sj′－1,k］,k＜wjsj′,max {M(j′)［l－1,k－∑sj′τ=l+1wj′τ］+∑sj′τ=l+1vj′τ,l=1,2,…,sj},k≥∑sj′i=1wj′i,max {M(j′)［sj′－1,k］,M(j′)［s(j′)－1,k－wj′sj′］+vj′sj′},wj′sj′≤k＜∑sji=1wj′i.
由1）、2）和3）可知，对于（ⅰ）、（ⅱ）和（ⅲ）三种情形证明了对于l=m+1（对应(i′,j′)），由递推公式（1）或（2）给出的M(j′)［i′,k］最大价值要求.
对于任意1≤l≤n（对应的(i,)）和任意k，由递推公式（1）或（2）给出的M(j)［i,k］为对应的最大价值.证毕.
为了动态规划表M求取最优子集，定义回溯表F来跟踪上述递推，行对应于每物品，列对应于背包的承重量.令
F(j)［i,k］=
0,M(j)［i,k］=M(j)［i－1,k－wji］+vji;sj－t,M(j)［sj,k］=M(j)［t,k－∑sjτ=t+2wjτ)］+∑sjτ=t+2vjτ, t=0,1,…,sj－2;1M(j)［i,k］=M(j)［i－1,k］.（3）
回溯以动态规划表M的M(r)［sr,T′］直到M(1)［0,0］，回溯策略教学论文描述为：
1）若F(j)［i,k］=0，则回溯至M(j)［i－1,k－wji］，此时令xji=1；
2）若F(j)［i,k］=1，则回溯至M(j)［i－1,k］，此时令xji=0；
3）若F(j)［i,k］=sj－t＞1，则回溯至M(j)［i－(sj－t),k－∑sjτ=t+2wjτ)］，此时令xjt+2=xjt+3=…=xjsj=1，xjt+1=0.
2[3]
发表评论
共有3000条评论 快来参与吧~