2.6基本算法之动态规划2989:糖果

描述

由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。

答案:

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int dp[1005][1005];//dp[i][j]:从i种糖果中选,组成糖果总数量k的倍数
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
memset(dp,-0x3f,sizeof(dp));/*边界条件:dp[i][j]初始化为负无穷,
除了dp[0][0]为0,因为我们这里求的是最大值,
另外,必须保证所有的状态是由dp[0][0]转移过来的*/
dp[0][0]=0;//dp[0][0]边界条件:0种糖果组成糖果总数量0的倍数是0 
for(int i=1;i<=n;i++){//从i种糖果中选
for(int j=0;j<k;j++){//求余数从0开始到k-1结束 
//1.不选 
if(j-a[i]%k>=0){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]%k]+a[i]);
}
//2.选 
else{
dp[i][j]=max(dp[i-1][j],dp[i-1][k-abs(j-a[i]%k)]+a[i]);
}
}
}
cout<<dp[n][0];
return 0;
}

感谢大家的不取关！我   来吗？？？   回来了！

原文地址：https://blog.csdn.net/Andy_SCP001/article/details/140674477

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！