HDU 2546 飯卡 簡單背包問題

分析：可分以下兩種情況，

a，當m小於５時答案就是本身．

b，當m>=５時，我們一般都會先將錢用到剩下不小於５卻最小時，最後再買價格最大(max)的那種才會使得最終結果最小，那麼就先把最大的那個存下來．問題就轉變成怎樣將(m-5)的錢花到最小q，這就是一個簡單的背包問題了．最後用q--max就 得到答案了．

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
#include<cctype>  
#include<iomanip>  
 
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<n;++i)cin>>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))<<endl; 
            continue; 
        } 
        memset(dp,0,sizeof(dp)); 
        dp[0]=1; 
        for(int i=0;i<n;++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<<m-q-max<<endl; 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iomanip>

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<n;++i)cin>>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))<<endl;
            continue;
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<n;++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<<m-q-max<<endl;
    }
    return 0;
}