george2222001 发表于 2008-4-26 16:56

求该背包问题的lingo程序！

著名的背包问题：一个背包最多只能装N公斤的东西。现有M件物品，重量分别为Wi，价格分别为Pi，应携带那些物品使得携带物品的价值最大? 该实例中，N = 200 (kg), 物品件数M = 20; 重量及价格见下表： 表.5 0-1背包数据重量32,22,5,16,14,18,4,27,19,13,17,6,20,26,20,28,29,18,29,16价格19,91,10,6,29,25,54,42,76,84,66,43,33,44,87,62,57,3,37,32:@L

dingd 发表于 2008-4-30 22:34

参考这个页面：
http://202.115.21.138/wlxt/ncourse/model/web/exercise/exercise/p3.htm

bainhome 发表于 2008-4-30 23:17

链接不错，赞一个！
只是最后那个MATLAB的穷举算法写得有点儿差劲...写了这么长时间代码，有日子没见过循环用这么恶心的了。:victory:
另外,0-1整数规划MATLAB有现成命令，不过从程序的流程结构上看，LINGO、1stopt等软件比MATLAB明显更加适合求解此类规划问题。

[ 本帖最后由 bainhome 于 2008-4-30 23:21 编辑 ]

woodballhead 发表于 2008-5-5 08:15

这个0-1规划太简单了，用LINGO、1stopt等软件来做这个问题简直是小菜。

zhh19880202 发表于 2008-7-9 13:19

0-1规划的模型还有哪些啊？？？
这种处理方法是很简单

jetcatty 发表于 2010-1-30 15:58

!著名的背包问题：一个背包最多只能装N公斤的东西。现有M件物品，重量分别为Wi，价格分别为Pi，应携带那些物品使得携带物品的价值最大? 该实例中，N = 200 (kg), 物品件数M = 20 重量及价格见下表：
重量32,22,5,16,14,18,4,27,19,13,17,6,20,26,20,28,29,18,29,16
价格19,91,10,6,29,25,54,42,76,84,66,43,33,44,87,62,57,3,37,32;
model:
sets:
M/1..20/:W,P,X;
endsets
data:
W=32,22,5,16,14,18,4,27,19,13,17,6,20,26,20,28,29,18,29,16;
P=19,91,10,6,29,25,54,42,76,84,66,43,33,44,87,62,57,3,37,32;
enddata
MAX=@SUM(M:X*P);
@FOR(M:@BIN(X));
@SUM(M:X*W)<=200;
end

jetcatty 发表于 2010-1-30 15:58

Global optimal solution found.
   Objective value:                              696.0000
   Extended solver steps:                               0
   Total solver iterations:                           0

                     Variable         Value      Reduced Cost
                        X( 1)      0.000000         -19.00000
                        X( 2)      1.000000         -91.00000
                        X( 3)      0.000000         -10.00000
                        X( 4)      0.000000         -6.000000
                        X( 5)      0.000000         -29.00000
                        X( 6)      0.000000         -25.00000
                        X( 7)      1.000000         -54.00000
                        X( 8)      0.000000         -42.00000
                        X( 9)      1.000000         -76.00000
                         X( 10)      1.000000         -84.00000
                         X( 11)      1.000000         -66.00000
                         X( 12)      1.000000         -43.00000
                         X( 13)      0.000000         -33.00000
                         X( 14)      1.000000         -44.00000
                         X( 15)      1.000000         -87.00000
                         X( 16)      1.000000         -62.00000
                         X( 17)      1.000000         -57.00000
                         X( 18)      0.000000         -3.000000
                         X( 19)      0.000000         -37.00000
                         X( 20)      1.000000         -32.00000
页: [1]
查看完整版本: 求该背包问题的lingo程序！