POJ 1787 Charlie's Change 背包问题 - c++编程基础

乍一看是多重背包问题，由于需要记录每种物品的个数。
既然每次在转移状态的时候知道每种物品的个数，便可以根据完全背包来做，这样效率将大大提高，代码也简洁。
num[i][j]表示总数为j的时候，i种硬币的个数
dp[j]表示总数为j的时候，最多的总硬币个数
[cpp]? www.2cto.com
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#define eps 1e-6?
#define LL long long?
#define LD long double?
#define pi acos(-1.0)?
#define inf 1<<30?
using namespace std;?

int m,cnt[4],cost[4]={1,5,10,25},num[4][10005],dp[10005];?
int main(){?
??? while(scanf("%d%d%d%d%d",&m,&cnt[0],&cnt[1],&cnt[2],&cnt[3])!=EOF&&m+cnt[0]+cnt[1]+cnt[2]+cnt[3]){?
??????? for(int i=1;i<=m;i++)?
??????????? dp[i]=-1;?
??????? dp[0]=0;?
??????? memset(num,0,sizeof(num));?
??????? for(int i=0;i<4;i++)?
??????????? for(int k=cost[i];k<=m;k++)?
??????????????? if(dp[k-cost[i]]!=-1&&dp[k] ??????????????????? dp[k]=dp[k-cost[i]]+1;?
??????????????????? num[i][k]=num[i][k-cost[i]]+1;?
??????????????????? for(int r=0;r ??????????????????????? num[r][k]=num[r][k-cost[i]];?
??????????????? }?
??????? if(dp[m]!=-1)?
??????????? printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",num[0][m],num[1][m],num[2][m],num[3][m]);?
??????? else?
??????????? printf("Charlie cannot buy coffee.\n");?
?
??? }?
??? return 0;?
}?
作者：ACM_cxlove