考虑用dp的做法，容易想到价格低的物品一定要比价格高的物品拿的优先级高，所以排序。
dp[i]表示取前i件物品需要的最少价格，当超越了价格，就不算。
转移方程为 dp[i]=min(dp[i-1]+a[i],dp[i-k]+a[i]) 表示当前物品单独买和买一送一的情况；
取最小值。
上代码
#include<bits/stdc++.h> using namespace std; int dp[200005]; int a[200005]; int main() { int t; cin>>t; while(t) { t--; int n,p,k; cin>>n>>p>>k; int ans=0; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); for(int i=1;i<=n;i++) { dp[i]=dp[i-1]+a[i]; if(i>=k){ dp[i]=min(dp[i],dp[i-k]+a[i]);} if(dp[i]<=p) { ans=i; } } cout<<ans<<endl; } }
Codeforces Round #610 (Div. 2).K for the Price of One (Hard Version)
原文：https://www.cnblogs.com/LH2000/p/12404253.html