[数据结构与算法]取余dp：配整

描述

一个数组，取一些数使得取的数之和尽可能大，但要求这个和必须是 的倍数。

输入描述：
第一行输入两个正整数 n 和 k
第二行输入 n 个正整数

输出描述：
如果没有合法方案，输出 -1。
否则输出最大的和。

示例1

输入：
5 5
4 8 2 9 1
输出：
20

说明：
取后四个数即可

思路

问题要求在一个数组中，选取一定数字组配成能够被k整除最大的和，若采取基本做法，那么需要计算每个数字是否加入到Sum中，并求和，复杂度为指数级别

采取动态规划dp[n][i]=k 表示前n个数字中选取一定量数字，使得sum%k=i 最大的和为k

递推方程

对于第n个数字，求解dp[n][i]

• 不加入到序列中 那么dp[n][i]=dp[n-1][i]
• 加入到序列中，那么arr[n]+dp[n-1][(k+j-arr[n]%k)%k]

其中(k+j-arr[n]%k)%k 累加上arr[n] 可以使得sum可以除k余j

在1、2中取较大值即可

代码

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> arr(n);
    vector<vector<long long>> dp(n+1,vector<long long>(k,-10000000000));  // dp[i][j]  表示前i个数字中   sum%k=j   的最大和   
 
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
       //每引入一个数 查询每个余数情况
        for(int j=0;j<k;j++)
        {
              dp[i][j]=max(dp[i-1][j],dp[i-1][(k+j-arr[i]%k)%k]+arr[i]);
        }
    }
    //最终结果是  所有数字中 余数为0的 最大和
    if(dp[n][0]<=0)
        cout<<-1<<endl;
    else
        cout<<dp[n][0]<<endl;
}

易错点

由于需要 i-1 所以可以增加辅助一列，同时初始化所有的元素 为足够小的负数，不能初始化为0 因为为0 那么dp[i][j]可以始终不断增大（dp[i-1][(k+j-arr[i]%k)%k]+arr[i]），但是实际情况可能不能组配出对应余数

最终的判定即为对应dp是否>0

节约内存做法：滚动数组

由于每次仅仅会使用到dp[i-1][] 因此采取滚动数组做法

由于无法使用一组一维数组完成滚动，因而采取 2个一维数组进行滚动
采取now next交替使用，工作数组覆盖历史数组

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> arr(n);
    vector<vector<long long>> dp(2,vector<long long>(k,-10000000000));  // dp[i][j]  表示前i个数字中   sum%k=j   的最大和   
    int now=0;  //当前使用的数组
    int next=1;  //下一组使用的序号
    
    
    dp[now][0]=0;
    for(int i=1;i<=n;i++)  //每一轮使用上一轮的 dp[] 
    {
        cin>>arr[i];
       //每引入一个数 查询每个余数情况
        for(int j=0;j<k;j++)
        {
              dp[next][j]=max(dp[now][j],dp[now][(k+j-arr[i]%k)%k]+arr[i]);
        }
        
        //每一轮计算，进行滚动  转移工作数组  每次覆盖
        now=now==1?0:1;  
        next=next==1?0:1;

    }
    //最终结果是  所有数字中 余数为0的 最大和
    if(dp[now][0]<=0)
        cout<<-1<<endl;
    else
        cout<<dp[now][0]<<endl;
}