题解 | #最小邮票数#

最小邮票数

http://www.nowcoder.com/practice/83800ae3292b4256b7349ded5f178dd1

用没有状态压缩的二维数组来动态规划

第i行考虑加入第i张邮票

第j列考虑目标面值为j

用结构体存每个位置凑出的最接近j的面值price和所需的最小张数num

最后看dp[N][M].price是否等于M，输出其num即可

比较烦人的是状态转移

#include<iostream>

using namespace std;

struct node {
    int price;
    int num;
};
int main(){
    
    int M,N;
    int value[21];
    value[0]=0;
    node dp[20][100];
    node n;
    n.price = 0;
    n.num = 0;
    for(int i=0;i<100;i++) dp[0][i] = n;
    for(int i=0;i<20;i++) dp[i][0] = n;
    
    while(cin>>M>>N){
        for(int i=1;i<=N;i++){
            cin>>value[i];
        }
        for(int i=1;i<=N;i++){
            for(int price=1;price<=M;price++){
                node doNothing = dp[i-1][price];
                
                    node last = dp[i-1][price-value[i]];
                    node selectIt;
                    selectIt.num = last.num+1;
                    selectIt.price = last.price+value[i];
                    if(selectIt.price<=price){
                        if(price-selectIt.price<price-doNothing.price){//选择以后更接近j，则选择
                            dp[i][price] = selectIt;
                        } else if(price-selectIt.price>price-doNothing.price){//否则不选
                            dp[i][price] = doNothing;
                        } else if(selectIt.num<doNothing.num){//如果选不选price都一样，则选num更小的
                            dp[i][price] = selectIt;
                        } else {
                            dp[i][price] = doNothing;
                        }
                    } else {
                        dp[i][price] = doNothing;
                    }
                
            }
        }
        int num = dp[N][M].num;
        if(dp[N][M].price==M){
            cout<<dp[N][M].num<<endl;
        } else {
            cout<<0<<endl;
        }
    }
    
    return 0;
}