POJ1252-Euro Efficiency-DP，完全背包（允许找零）

参考这里：

允许找零应该怎么做： http://www.4ucode.com/Study/Topic/2119680

实在不会看这里： http://hi.baidu.com/wy_erhu/blog/item/057fed168e02660d972b4331.html

 

 

我最初的代码是不考虑找零的完全背包：（代码）

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

/*
  心得：
        1. （多重）物品编号 编号从1开始比较好写代码 
        2. 这个代码的错误是： 只考虑付款相加的情况，不考虑找零 
*/

#define INF 1<<27

int w[7];       //value of each banknote
int f[7][101];  //f[i][j]: w[1...i] considered, the least # of banknotes to amount up to j

//DP(完全背包)
void solve(){
     memset(f,-1,sizeof(f));
     
     int i,j,k,k_max;
     //DP(完全背包) init
     f[0][0]=0;
     
     //DP(完全背包)
     for(i=1;i<=6;i++){
         k_max=100/w[i];//∴币种w[i]的数量范围是[0,k_max] 
         for(j=0;j<=100;j++){
             /*
               初始化： 
               f[i][j]=-1
               f[0~6][0]=0
               
               状态转移方程： 
               f[i][j]=min{f[i-1][j-k*w[i]]+k}, 0<=k<=100/w[i]
             */
             int temp=INF;
             for(k=0;k<=k_max;k++){
                 if(j-k*w[i]>=0 && f[i-1][j-k*w[i]]!=-1 && f[i-1][j-k*w[i]]+k<temp){
                     temp=f[i-1][j-k*w[i]]+k;
                 }
             }
             f[i][j]=temp;
         }
     } 
     //题目保证结束时，f[5][0~100]都能找到解 ——至少可以用全部为1的币种来构造:) 
}

void output(){
     double sum=0;
     int max=-1;
     
     int i;
     for(i=1;i<=100;i++){
         printf("%d\t",f[6][i]);
         sum+=f[6][i];
         if(f[6][i]>max)
             max=f[6][i];
     } 
     printf("%lf %d\n",sum/100, max);
}

int main(){
    int cases;
    scanf("%d",&cases);
    while(cases-->0){
        int i;
        for(i=1;i<=6;i++){
            scanf("%d",&w[i]);
        }
        solve();
        output();
    }
    
    system("pause");
    return 0;
}

 

可以找零时做两次完全背包：（代码）

#include<iostream>        //完全背包
#include<stdio.h>
#include<algorithm>
using namespace std;    
int main()    
{
    int cases,euro[10],dp[20000],maxn;
    cin>>cases;
    while(cases--)
    {
        for(int i=1;i<=6;++i)
            cin>>euro[i];
        
        /*
           最多付款的数目(比如人民币中付款49，则可以先付50，找回1，则50称为最多付款的数目)肯定小于
           (100/euro[1])*euro[6]+100，因为如果达到这个值，则需要找零至少100/euro[1]=100才能回到[1,100]的范围，这样还不如直接用euro[1]来付款
        */
        maxn=(100/euro[1])*euro[6]+100;       //上界
        fill(dp,dp+maxn,-1);
        dp[0]=0;

        /*
          1. 考虑每种币值可以进行"加"运算
          (这是传统的完全背包问题) 
          dp[i][j]=min{dp[i-1][j],dp[i][j-euro[i]]+1}, i=1~6, j∈[0,maxn] 
          case1: 没有付出euro[i] || case2: 考虑“再”付出 一个euro[i] 
        */    
        for(int i=1;i<=6;++i)    // 加运算
        {
            for(int j=euro[i];j<=maxn;++j)    
                if(dp[j-euro[i]]!=-1)
                {
                    if(dp[j]==-1)
                        dp[j]=dp[j-euro[i]]+1;
                    else
                        dp[j]=min(dp[j],dp[j-euro[i]]+1);
                }
        }

        /*
          2. 考虑每种币值可以进行"减"运算
          (这是一个小扩展——“可以找零 ”) 
          dp[i][j]=min{dp[i-1][j],dp[i][j+euro[i]]+1}, i=1~6, j∈[0,maxn] 
          case1: 没有找回euro[i]  || case2: 考虑“再”找回 一个euro[i] 

          注意：因为dp[i][j+euro[i]]中j+euro[i]>j，导致这里要用逆序循环。所以不能死记硬背“0-1背包”用逆序循环，最好自己想一想（脑海里形成一幅二维图像）
       */
        for(int i=1;i<=6;++i)    // 减运算
        {
            for(int j=maxn-euro[i];j>0;--j)        //因为是减,所以要逆序循环
                if(dp[j+euro[i]]!=-1)
                {
                    if(dp[j]==-1)
                        dp[j]=dp[j+euro[i]]+1;
                    else
                        dp[j]=min(dp[j],dp[j+euro[i]]+1);
                }
        }
        double ave=0;
        for(int i=1;i<=100;++i)
            ave+=dp[i];
        printf("%.2f %d\n",ave/100,*max_element(dp+1,dp+101));
    }
    return 0;
}