0-1背包问题具有最优子结构性质？ 关键在于不能把一个商品拿走多次。在背包容量为W时，其最优结构

0-1背包问题具有最优子结构性质？ 关键在于不能把一个商品拿走多次。在背包容量为W时，其最优结构

int bag_recur(int i, int v, vector>&table){
if (i == 0){
return costs[0] <= v ? values[0] : 0;
}
else{
if (table[i][v] == -1){
int max_1,max_2,max_;
max_1 = bag_recur(i-1,v,table);
if (v >= costs[i])
max_2 = bag_recur(i - 1, v - costs[i], table) + values[i];
else
max_2 = 0;
if (max_1 < max_2)
max_ = max_2;
else
max_ = max_1;
table[i][v] = max_;
}
return table[i][v];
}
}i初始是物品总数目-1，v是总负重量。

costs对应的物品位置存储物品的负重

values对应的位置存储物品的价值。


最优子结构的性质算法导论上面说的很多，我也没太理解。LZ也在读吗？

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息