hdu 2546 飯卡( 01背包 )

2019-11-11 04:21:18

字體：大中小

來源：轉載

供稿：網友

飯卡

Time Limit: 5000/1000 MS (java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 25971 Accepted Submission(s): 9066PRoblem Description電子科大本部食堂的飯卡有一種很詭異的設計，即在購買之前判斷余額。如果購買一個商品之前，卡上的剩余金額大于或等于5元，就一定可以購買成功（即使購買后卡上余額為負），否則無法購買（即使金額足夠）。所以大家都希望盡量使卡上的余額最少。某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的余額，問最少可使卡上的余額為多少。 Input多組數據。對于每組數據：第一行為正整數n，表示菜的數量。n<=1000。第二行包括n個正整數，表示每種菜的價格。價格不超過50。第三行包括一個正整數m，表示卡上的余額。m<=1000。n=0表示數據結束。 Output對于每組輸入,輸出一行,包含一個整數，表示卡上可能的最小余額。 Sample Input

1505101 2 3 2 1 1 2 3 2 1500 Sample Output-4532 SourceUESTC 6th Programming Contest Online簡單的0-1背包問題：動態轉移方程：dp[1001]={0};背包為m, 每次的花費為a[i] for(i=0;i<n;i++)//進行n次遞推   for(j=m;j>=a[i];j--)  dp[j]=max(dp[j-a[i]]+a[i],dp[j]);解題思路：先排序   取出花費最大的值求出背包為m-5的花費的最小值最后m - dp[m-5] - (max)price[i]#include<iostream>#include<string>#include<string.h>#include<math.h>#include<algorithm>using namespace std;int main(){	int n;	while(cin>>n,n!=0)	{		int a[1001],m,i,j,dp[1001]={0};		for(i=0;i<n;i++)		    cin>>a[i];		cin>>m;		sort(a,a+n);//排序		if(m<5)		cout<<m<<endl;		else		{ 			for(i=0;i<n-1;i++)//進行n次遞推			{			  for(j=m-5;j>=a[i];j--) 			  {dp[j]=max(dp[j-a[i]]+a[i],dp[j]);		      }		  }		cout<<m-dp[m-5]-a[n-1]<<endl;	   }			}}