饭卡

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;	   }			}}