c - 最小总和的最优选择

Question

这是竞争性程序员手册中的一个问题:
我们得到的价格为k 产品超过n天，我们想每种产品只购买一次。然而， 我们一天最多可以购买一种产品。最少总数是多少 价格？

<表类=“s-表”> <标题> 日 0 1 2 3 4 5 6 7 <正文> 产​​品0 6 9 5 2 8 9 1 6 产​​品1 8 2 6 2 7 5 7 2 产​​品2 5 3 9 7 3 5 1 4

最佳选择是:

• 第 3 天的产品 0，价格为 2，
  
• 第 1 天的产品 1，价格为 2，
  
• 产品 2 在第 6 天以价格 1 销售。
  

总共为 5。

解决办法:
我们要么当天不购买任何产品d或购买产品x 属于集合 S 。在后一种情况下，我们删除 x来自集合S并添加价格x总价。

这是书中的代码:

#include <stdio.h>
#ifndef min
    #define min(a, b) ((a) < (b) ? (a) : (b))
#endif

int main()
{
    int price[3][8] = {{ 6, 9, 5, 2, 8, 9, 1, 6 },
                       { 8, 2, 6, 2, 7, 5, 7, 2 },
                       { 5, 3, 9, 7, 3, 5, 1, 4 }};
    int n = 8, k = 3;
    int total[1<<10][10];
    //Buy all products on day 0
    for (int x = 0; x < k; x++) {
        total[1<<x][0] = price[x][0];
    }

    for (int d = 1; d < n; d++) {
        for (int s = 0; s < (1<<k); s++) {
            total[s][d] = total[s][d-1];
            for (int x = 0; x < k; x++) {
                if (s & (1<<x)) {
                    total[s][d] = min(total[s][d], total[s ^ (1<<x)][d-1] + price[x][d]);
                    break;
                }
            }
        }
    }
    //Output    
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf("%d", total[i][j]);
        }
        printf("\n");
    }
}

这个问题限制我们每天只能购买一种产品，但代码似乎根本没有解决这个问题(而且，我们在第一天购买所有产品，这很好)。输出只是当天可用的每种产品的最小值 [1,2,1]。我在这里做错了什么？

Answer 1

在调试器中花了相当长的时间后，我能够使书中的算法发挥作用。可以说书中提供的代码片段完全被破坏了。

最重要的修改:

1. 如果我们从相邻的和中更新它，我们只会更新更复杂的和，也就是说，我们不会根据 001 或 010 的和更新 111 处的和。我们使用 __builtin_popcount 来查找当前设置索引与我们尝试更新的索引之间的差异。

2. 如果已经过去了足够的天数来满足先前组的需求，我们只会更新更高的订单组。

我希望我没有在这里犯错误(再次)。如果我这样做了，请随时纠正我。这次我确实尝试验证多个输入，这似乎有效。

请注意，我使用了多个完全不必要的局部变量。我只是想要一些清晰度和可读性。

这本质上与书中的算法相同，但有一组正确运行所必需的限制。如果没有这些限制，它会添加完全不兼容的内容或在错误的时间添加并最终无法工作。

该算法确实解决了您每天只能在 sol[xorIndex][dayIndex-1] + currentPrice 部分购买 1 件商品的问题。正在访问的 sol 部分在前天填充了不我们要添加的项目。

int optimalSelection(int products, int days, int prices[products][days]){
    int sol[1<<products][days];
    memset(sol, 0, sizeof(sol));
    for (int x = 0; x < products; x++) {
        sol[1<<x][0] = prices[x][0];
    }

    for (int dayIndex = 1; dayIndex < days; dayIndex++) {
        int allPossibleSetsCount = 1<<products;
        for (int setIndex = 0; setIndex < allPossibleSetsCount; setIndex++) {
            int currentMin = sol[setIndex][dayIndex-1];
            for (int productIndex = 0; productIndex < products; productIndex++) {
                if (setIndex&(1<<productIndex)) {
                    // this is the index of the set WITHOUT current product
                    int xorIndex = setIndex^(1<<productIndex);
                    if(__builtin_popcount(xorIndex) > dayIndex)
                        continue;

                    if (__builtin_popcount(setIndex ^ xorIndex) == 1){
                        // minimum for the prior day for the set excluding this product
                        int previousMin = sol[xorIndex][dayIndex-1];
                        // current price of the product
                        int currentPrice = prices[productIndex][dayIndex];
                        sol[setIndex][dayIndex] = currentMin == 0 ? previousMin + currentPrice : std::min(previousMin + currentPrice, currentMin);
                        currentMin = sol[setIndex][dayIndex];
                    }

                }
            }
        }
    }

    return sol[(1<<products)-1][days-1];
}