求该背包问题的lingo程序！

george2222001

著名的背包问题：一个背包最多只能装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

参考这个页面：
http://202.115.21.138/wlxt/ncour ... ise/exercise/p3.htm

bainhome

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

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

woodballhead

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

zhh19880202

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

jetcatty

!著名的背包问题：一个背包最多只能装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

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