二重背包问题.pdfVIP

二重背包代码 代码： model : sets: goods/g1..g5/:v,w,c,x; endsets !建立一个集合含有5个包：g1~g5，并定义属性v:体积；w:质量；c:价值；x： 0-1变量（代表取或者不取）; data: w=2 1 2 3 4; v=3 6 3 6 3; c=10 7 10 9 11; enddata !输入5个包的属性数据; max=@sum(goods:c*x); @sum(goods:w*x)=9; @sum(goods:v*x)=11; @for(goods:@bin(x)); end !编写目标函数和约束条件; 运行结果： 价值最优值：31 选择g1,g3,g5 三个包 为最优解 二重背包问题的状态转移方程 设第i 个背包的体积为v ，质量为w ，价值为c ，令m(i,j,k) i i i 表示背包容积j ，最大载重k ，可选物品为第i~n 个背包时问 题的最优值，则建立状态转移方程如下：  max m i 1, j, k , m i 1, j v , k w c 若j  v 且k  w      i i  i  i i m i, j,k    m i 1, j ,k 若0  j  v 或0  k  w    i i  c 若j  v 且k  w  m n, j, k   n n n 0 若0  j v n 或0 k w n  例子：若物品数量n=5 个，背包容量为4，最大载重为5， v={1,2,1,2,1}，w={3,1,1,1,2}，c={7,3,5,4,6}，根据递归关系式 计算如下动态规划表： i=5 j\k 1 2 3 4 5 1 0 6 6 6 6 2 0 6 6 6 6 3 0 6 6 6 6 4 0 6 6 6 6 i=4 j\k 1 2 3 4 5 1 0 6 6 6 6 2 4 6 6 6