vcgaoshou 2024-06-27 18:11 采纳率: 71.4%
浏览 12
已结题

用动态规划算法均分纸牌

有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;
}

  • 写回答

15条回答 默认 最新

  • 叫兽-郭老师 Java领域新星创作者 2024-06-27 18:13
    关注

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

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

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

    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] + cdp[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] 就是最终的最小移动代价。
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(14条)

报告相同问题?

问题事件

  • 系统已结题 7月6日
  • 已采纳回答 6月28日
  • 创建了问题 6月27日

悬赏问题

  • ¥15 Apache显示系统错误3该如何解决?
  • ¥30 uniapp小程序苹果手机加载gif图片不显示动效?
  • ¥20 js怎么实现跨域问题
  • ¥15 C++dll二次开发,C#调用
  • ¥15 请教,如何使用C#加载本地摄像头进行逐帧推流
  • ¥15 Python easyocr无法顺利执行,如何解决?
  • ¥15 求一个十多年前的国产符号计算软件(MMP)+用户手册
  • ¥15 为什么会突然npm err!啊
  • ¥15 java服务连接es读取列表数据,服务连接本地es获取数据时的速度很快,但是换成远端的es就会非常慢,这是为什么呢
  • ¥15 vxworks交叉编译gcc报错error: missing binary operator before token "("