用动态规划算法均分纸牌

Question

有n堆卡片，每堆卡片的张数不同，总的张数不一定是n的倍数。在任意两堆卡片之间，移动任意张卡片，最终目标是让最多一堆的卡片张数与最少一堆的卡片张数的差小于等于1。规定将第i堆上的一张卡片移动到第j堆上，或者相反移动，代价均为|i-j|。用动态规划算法计算均分纸牌的代价。例如当n=5，每堆张数分别是5,9,2,12,9时，最小移动代价是8。代码如下
请问
1.解释dp[i][j]的含义
2.如何理解代码中A、B行的状态转移方程
3.题目中从第i堆移动一张卡片到第j堆上，或者相反移动，代价均为|i-j|，在程序中是如何计算|i-j|的

部分代码如下：
const int M=10;
long dp[M][M],card[M],s[M];
int main(){
    int n,i,j;
    cin>>n;
    for (i=1;i<=n;i++){
        cin>>card[i];
        s[i]=s[i-1]+card[i];
    }
    int r=s[n]%n,q=s[n]/n;
    for(i=1;i<=n;++i){ 
        for(j=0;j<=r;++j){ 
            int c=abs(s[i]-q*i-j);
            dp[i][j]=dp[i-1][j]+c;//A
            if(j)
                dp[i][j]=min(dp[i-1][j-1]+c,dp[i][j]);//B
        }
    }
    cout<<dp[n][r]<<endl;
    return 0;
}

Answer 1

🕗晚上好，题主！目前：🟢[在线]
📢参考通义千问、由郭老师整理提供！
📣今日诗号：窗外日光弹指过，席间花影坐前移。

动态规划算法均分纸牌代码解析

你提供的代码使用动态规划算法解决了均分纸牌问题，下面我将详细解释代码的各个部分：

1. dp[i][j] 的含义:

dp[i][j] 表示前 i 堆纸牌，使得其总和与平均值之差为 j 时，需要的最小移动代价。

• i：表示考虑了前 i 堆纸牌 (1 ≤ i ≤ n)
• j：表示前 i 堆纸牌的总和与平均值之差 (0 ≤ j ≤ r, r 为总牌数对 n 的余数)

2. 状态转移方程的理解:

• A 行代码：dp[i][j]=dp[i-1][j]+c;

  这行代码表示不调整第 i 堆纸牌的情况。

  • c = abs(s[i] - q * i - j) 计算了前 i 堆纸牌的实际总和与目标总和之间的差值。目标总和是 q * i + j，其中 q 是平均值，j 是与平均值的差值。
  • dp[i][j] = dp[i-1][j] + c 表示前 i 堆纸牌与平均值之差为 j 的最小代价，等于前 i-1 堆纸牌与平均值之差也为 j 的最小代价加上第 i 堆纸牌与目标值之间的差值。

• B 行代码：dp[i][j]=min(dp[i-1][j-1]+c,dp[i][j]);

  这行代码表示调整第 i 堆纸牌的情况，将其与前一堆纸牌进行调整。

  • dp[i][j] = min(dp[i-1][j-1] + c, dp[i][j]) 表示在两种情况下取最小值：
    • 从前一堆移动一张牌到当前堆：dp[i-1][j-1] + c，此时前 i-1 堆的总和与平均值的差为 j-1，移动一张牌的代价为 c。
    • 不从前一堆移动牌：dp[i][j]，即 A 行代码计算的结果。

3. |i - j| 的计算:

在代码中，并没有直接计算 |i - j|。 这是因为动态规划算法通过状态转移方程，隐含地计算了移动的代价。

• 在 A 行代码中，假设不调整第 i 堆，则代价为 c = abs(s[i] - q * i - j)，这个代价实际上就包含了所有需要从其他堆移动到第 i 堆（或从第 i 堆移动到其他堆）的牌的数量，也就是 |i - j| 的总和。
• 在 B 行代码中，通过比较 dp[i-1][j-1] + c 和 dp[i][j]，隐含地比较了将一张牌从 i-1 堆移动到 i 堆，或者不移动的代价，从而找到了最小代价。

完整代码:

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int M = 10;
long dp[M][M], card[M], s[M];

int main() {
    int n, i, j;
    cin >> n;

    // 计算前缀和
    for (i = 1; i <= n; i++) {
        cin >> card[i];
        s[i] = s[i - 1] + card[i];
    }

    int r = s[n] % n, q = s[n] / n; // r: 余数, q: 平均值

    // 初始化 dp 数组
    for (i = 0; i <= n; ++i) {
        for (j = 0; j <= r; ++j) {
            dp[i][j] = 1e9; // 初始化为一个很大的值
        }
    }
    dp[0][0] = 0; // 初始状态

    for (i = 1; i <= n; ++i) {
        for (j = 0; j <= r; ++j) {
            int c = abs(s[i] - q * i - j);
            dp[i][j] = dp[i - 1][j] + c; // 不调整第 i 堆
            if (j) 
                dp[i][j] = min(dp[i - 1][j - 1] + c, dp[i][j]); // 调整第 i 堆
        }
    }

    cout << dp[n][r] << endl; 
    return 0;
}

代码解释:

1. 输入纸牌堆数 n 和每堆的纸牌数。
2. 计算纸牌总数的前缀和 s[i]。
3. 计算平均值 q 和总牌数对 n 的余数 r。
4. 初始化 dp 数组，将所有元素初始化为一个很大的值，并将 dp[0][0] 初始化为 0。
5. 使用两层循环遍历所有状态，并根据状态转移方程计算 dp[i][j] 的值。
6. 最终 dp[n][r] 就是最终的最小移动代价。