Picat求解0-1背包问题未最大化价值，无物品选中求助

问题根源 #

你的代码中计算总重量和总价值的列表推导式逻辑错误，导致约束条件仅能被全选0的情况满足。具体来说：

TotalWeight #= sum([ W * T : W in Weights, T in Take]),

这个表达式会生成所有重量与所有Take变量的乘积组合（共N×N项，N为物品数量）后求和，而非对应物品的重量与选取状态的乘积之和。这种错误计算出的总重量远超过背包容量，只有当所有Take为0时，总重量才为0，满足TotalWeight <= 58的约束。

修复方案 #

需要将重量和Take变量按对应位置配对后再求和，以下两种写法均可：

方法1：通过索引遍历 #

利用物品数量N，按索引访问对应位置的重量和Take变量：

TotalWeight #= sum([ Weights[I] * Take[I] : I in 1..N ]),
TotalVal #= sum([ Vals[I] * Take[I] : I in 1..N ]),

方法2：使用zip函数配对 #

通过zip/2函数将重量列表和Take数组配对，遍历每一对元素计算乘积：

TotalWeight #= sum([ W * T || (W,T) in zip(Weights, Take) ]),
TotalVal #= sum([ V * T || (V,T) in zip(Vals, Take) ]),

修复后的完整代码 #

import sat.
import util.

main(Args) =>
    solve_knap(Args).

solve_knap(Args) =>
    Params = open(Args[1]),
    MaxWeight = to_int(read_line(Params)),
    ValsStr = split(read_line(Params),","),
    N = len(ValsStr),
    Vals = [to_int(X) : X in ValsStr],
    WeightsStr = split(read_line(Params),","),
    Weights = [to_int(X) : X in WeightsStr],

    Take = new_array(N),
    Take :: 0..1 ,
    TotalWeight #= sum([ Weights[I] * Take[I] : I in 1..N ]),
    TotalWeight #<= MaxWeight ,

    TotalVal #= sum([ Vals[I] * Take[I] : I in 1..N ]),

    solve([$max(TotalVal),$report(printf("Found %d\n",TotalVal))],Take),

    println(TotalWeight),
    println(MaxWeight),
    println(Take).

验证说明 #

修复后运行代码，求解器会正确计算对应物品的总重量与总价值，找到满足背包容量约束的最大价值组合，而非全0的无效解。

内容的提问来源于stack exchange，提问作者Mr Felix U