HDU 2546 饭卡 简单背包问题

分析：可分以下两种情况，

a，当m小于５时答案就是本身．

b，当m>=５时，我们一般都会先将钱用到剩下不小于５却最小时，最后再买价格最大(max)的那种才会使得最终结果最小，那么就先把最大的那个存下来．问题就转变成怎样将(m-5)的钱花到最小q，这就是一个简单的背包问题了．最后用q--max就 得到答案了．

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int inf=10000000;

int f[1005];
int dp[1005];

int main(){
int n;
while(cin>>n&&n){
for(int i=0;i>f[i];
int max=*max_element(f,f+n);///先记下最大的那个价格
*max_element(f,f+n)=0;
int m; cin>>m;
if(m<=5){
cout<<(m<5 m:(m-max))< continue;
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i for(int j=m-5;j>=f[i];--j)
if(dp[j-f[i]])dp[j]=1;
int q;///大于５且能到达的最小数
for(q=m;!dp[q];--q);
cout< }
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int inf=10000000;

int f[1005];
int dp[1005];

int main(){
int n;
while(cin>>n&&n){
for(int i=0;i>f[i];
int max=*max_element(f,f+n);///先记下最大的那个价格
*max_element(f,f+n)=0;
int m; cin>>m;
if(m<=5){
cout<<(m<5 m:(m-max))< continue;
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i for(int j=m-5;j>=f[i];--j)
if(dp[j-f[i]])dp[j]=1;
int q;///大于５且能到达的最小数
for(q=m;!dp[q];--q);
cout< }
return 0;
}