首页
标准01背包问题是np-hard,如果物品的价值都为1,是否就不是np-hard的了?
2024-12-04 阅读 82
即使物品的价值都为1,标准01背包问题仍然是NP-hard的。因为标准01背包问题是NP难题,即至少和NP中的问题一样难解。价值为1只是影响问题的具体表述,但不影响问题的难度。NP-hard问题是指那些至少和NP问题一样难解的问题,而NP问题是可以在多项式时间内验证解的问题。
更新于 2024年12月07日