完全背包记录路径poj1787 好题

这题有点多重背包的感觉，但还是用完全背包解决，dp[j]表示凑到j元钱时的最大硬币数，pre[j]是前驱，used[j]是凑到j时第i种硬币的用量

△回溯答案时i-pre[i]就是硬币价值

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int v[4]={1,5,10,25},num[4],ans[1000];
int p,dp[10010],pre[10010],used[10010];//记录回溯状态，记录每个状态用了多少硬币 

int main(){
    while(scanf("%d",&p)){
        for(int i=0;i<4;i++)scanf("%d",&num[i]);
        if(!p)break;
        memset(dp,-0x3f,sizeof dp);
        pre[0]=-1,dp[0]=0;
        for(int i=0;i<4;i++){
            memset(used,0,sizeof used);
            for(int j=v[i];j<=p;j++)
                if(dp[j-v[i]]>=0&&dp[j-v[i]]+1>dp[j]&&used[j-v[i]]<num[i]){
                    dp[j]=dp[j-v[i]]+1;
                    used[j]=used[j-v[i]]+1;
                    pre[j]=j-v[i];
                }
        }
        memset(ans,0,sizeof ans);
        if(dp[p]<0){
            puts("Charlie cannot buy coffee.");
            continue;    
        }
        else{
            int i=p;
            while(pre[i]>=0){
                ans[i-pre[i]]++;
                i=pre[i];
            }
        }
        printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
",ans[v[0]],ans[v[1]],ans[v[2]],ans[v[3]]);
    }
}