如何解决（或命名）这种类似背包的算法
How to solve (or name) this knapsack-like algorithm
假设我拥有一家商店并且只出售两件商品。
- 如果我卖铅笔和橡皮，我赚 3 美元
- 如果我卖铅笔和大理石，我赚 2 美元
- 如果我卖了一把尺子和一块橡皮，我赚了 2 美元
每个客户都愿意购买最多 1 件商品，我希望利润最大化。因此，出售 #1 和 #2 是非法的，因为那将是 2 支铅笔。由于橡皮擦，#1 AND #3 也是非法的。所以，合法的走法是：只有#1，只有#2，只有#3，或者#2 AND #3。由于最后一个选项的利润为 5 美元，我应该这样做。
如何在多项式时间内解决这个问题？如果它是 np-hard，什么启发式方法可能会让我接近？如果不出意外，这个问题有名字吗？
匹配一般（非二分）图，可通过 Blossom algorithm.
在多项式时间内求解
假设我拥有一家商店并且只出售两件商品。
- 如果我卖铅笔和橡皮，我赚 3 美元
- 如果我卖铅笔和大理石，我赚 2 美元
- 如果我卖了一把尺子和一块橡皮，我赚了 2 美元
每个客户都愿意购买最多 1 件商品，我希望利润最大化。因此，出售 #1 和 #2 是非法的，因为那将是 2 支铅笔。由于橡皮擦，#1 AND #3 也是非法的。所以，合法的走法是：只有#1，只有#2，只有#3，或者#2 AND #3。由于最后一个选项的利润为 5 美元，我应该这样做。
如何在多项式时间内解决这个问题？如果它是 np-hard，什么启发式方法可能会让我接近？如果不出意外，这个问题有名字吗？
匹配一般（非二分）图，可通过 Blossom algorithm.
在多项式时间内求解