贪心深搜,从最小的开始减,直到满足条件
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=101;
int can[N];
//int f[N][N];
int n,k;
long long minn=-1; //minn代表至少是多少,否则减枝
int dfs(long long now,int pos)
{
if(!(now%k))
{ minn=max(minn,now);
return now;}
if(now<minn)return 0;
if(pos==n)return 0;
long long a=dfs(now-can[pos],pos+1),b=dfs(now,pos+1);
return a>b?a:b;
}
int main()
{
cin>>n>>k; //要求k倍
long long ans=0;
for(int i=0;i<n;i++)
cin>>can[i],ans+=can[i];
sort(can,can+n);
cout<<dfs(ans,0);
}
顺带一提DP的做法是
f[i][j] i个内,余数是j 的数量的最大值
我的dfs剪枝剪不明白,看了你的恍然大悟,感谢