---
title: "糖果"
created: 2025-11-28
tags:
  - 算法
---

# 糖果

## 题目 [糖果](https://www.acwing.com/problem/content/description/1049/)

![[image-bfd34f5b.png]]

## 思路分析

N件产品中 任选若干件 (每件都包含数量不同的糖果）

N个物品 每个物品包含糖果数是他的价值w[i]

希望w[i] 最大 且 为K的整数倍

物品不可拆分 只能选与不选（01背包）

体积无限制

## 代码实现

dfs （tle）

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=110;

int w[N];

int n,k;

int res=0;

void dfs(int u,int sum){

	if(u>n){

		if(sum%k==0){

			res=max(res,sum);

		}

		return;

	}

	dfs(u+1,sum+w[u]);

	dfs(u+1,sum);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++){

		cin>>w[i];

	}

	dfs(1,0);

	cout<<res;

	return 0;

}
```

dp：

不能简单的推f[i]为考虑到第i件物品时 能达到的最大的数量

因为最大的数量不一定是%k==0的最大数量

这样会忽略正确答案

但其实发现它并不是没有体积的限制 限制是关于 %k余数是多少

dp(i,j)代表前i个物品总价值%k=j的集合

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=110;

int w[N];

int n,k;

int res=0;

int dp[N][N]; //前i件物品中选 得到价值之和mod k == j时的最大价值和

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++){

		cin>>w[i];

	}

	for(int j=0;j<k;j++)	dp[0][j]=-inf; // 一个物品不选 模k==j 为无效状态

	dp[0][0]=0; // 一个物品都不选 模 k为 0 和为 0

	for(int i=1;i<=n;i++){

		// 不选

		for(int j=0;j<k;j++){

			dp[i][j]=dp[i-1][j];

		}

		// 选

		for(int j=0;j<k;j++){

			if(dp[i-1][j]>=0){

				int mod = (j+w[i])%k;

				dp[i][mod] = max(dp[i][mod],dp[i-1][j]+w[i]);

			}

		}

	}

	cout<<dp[n][0];

	return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=110;

int w[N];

int n,k;

int res=0;

int dp[N][N]; //前i件物品中选 得到价值之和mod k == j时的最大价值和

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++){

		cin>>w[i];

	}

	for(int j=0;j<k;j++)	dp[0][j]=-inf; // 一个物品不选 模k==j 为无效状态

	dp[0][0]=0; // 一个物品都不选 模 k为 0 和为 0

	for(int i=1;i<=n;i++){

		for(int j=0;j<=k-1;j++){

			dp[i][j] = max(dp[i - 1][j], dp[i - 1][((j - w[i]) % k + k) % k] + w[i]);

		}

	}

	cout<<dp[n][0];

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[数字组合|数字组合]] 🏠 [[00-刷题理模型]] ➡️ [[装箱问题|装箱问题]]