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<<27int w[7]; //value of each banknoteint 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;}??
?
?