AcWing 1047. 糖果【动态规划】【01背包问题】【《信息学奥赛一本通》】

一、题目链接二、题目分析

（一）算法标签（二）解题思路 三、AC代码四、其它题解

AcWing 1047. 糖果

DP 01背包问题

解法一:

#include 
#include 
#include 

using namespace std;

const int N = 110;

// f[i][j]表示从前i个物品中选，总价值除以k余j的方案的
// 选第i个物品:f[i - 1][(j - w) % k] + w , 余数为(j - w) % k     (因为前i个总和%k=j，前i-1个总和%k余(j-w)%k)
// 不选第i个物品:f[i - 1][j]: 前i-1个总和%k还是j
int f[N][N];
int n, k;
int w;

// 取a % b 的正余数
int get_mod(int a, int b)
{
    return (a % b + b) % b;
}
int main()
{
    cin >> n >> k;
    
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w);
        for (int j = 0; j < k; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i - 1][get_mod(j - w, k)] + w);
        }
    }
    cout << f[n][0];
    return 0;
}

AcWing 1047. 糖果