杭电ACM——2546，饭卡（DP）

一维背包问题。
突破口：将菜的价格从小到大排序，对前n-1个物品进行DP，找出消费金额不超过m-5的方案中最大的消费金额sum，在此基础上，m - (sum+price[n]) 即为卡内最小余额。
因此，我们DP应在余额为0~m-5之内找出最优的解。
状态：dp[i,j]为在前i种菜中，当余额为j时，所能进行的最大消费。
状态转移方程：
dp[i,j]=
if(j<price[i]) dp[i,j]=dp[i-1,j];（不可选）
else dp[i,j]=max(dp[i-1,j],dp[i-1,j-p[i]]+p[i]);（可选，选与不选都试一遍）
边界处理：dp[0,0~m]=0。
最优解dp[n-1,m-5]。

代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
int dp[maxn][maxn],p[maxn];
//可以用滚动数组，减小空间复杂度，见后面另一个代码
int main()
{
int n,m,i,j;
while(~scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
sort(p+1,p+1+n);
scanf("%d",&m);
for(i=0;i<=m-5;i++)
dp[0][i]=0;
if(m<5)	printf("%dn",m);	//m<5啥也买不了
else
{
for(i=1;i<=n-1;i++)
for(j=0;j<=m-5;j++)
//j的范围为0~m-5
if(j<p[i])
dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-p[i]]+p[i]);
printf("%dn",m-dp[n-1][m-5]-p[n]);
}
}
return 0;
}

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
int dp[maxn],p[maxn];
int main()
{
int n,m,i,j;
while(~scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
sort(p+1,p+1+n);
scanf("%d",&m);
for(i=0;i<=m-5;i++)
dp[i]=0;
if(m<5)	printf("%dn",m);
else
{
for(i=1;i<=n-1;i++)
for(j=m-5;j>=p[i];j--)
dp[j]=max(dp[j],dp[j-p[i]]+p[i]);
printf("%dn",m-dp[m-5]-p[n]);
}
}
return 0;
}

最后

以上就是优雅发夹为你收集整理的杭电ACM——2546，饭卡（DP）的全部内容，希望文章能够帮你解决杭电ACM——2546，饭卡（DP）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。