POJ 1276 Cash Machine 【DP】

多重背包的模型，但一开始直接将N个物品一个一个拆，拆成01背包竟然T了！！好吧OI过后多久没看过背包问题了，翻出背包九讲看下才发现还有二进制优化一说。。。。。。。。就是将n个物品拆成系数：1,2,4，8....*物品价值和空间的物品，在这题中只要乘上money[i]就行了，从二进制考虑发现，这样可以组成0~n中所有的数

#include <iostream>

#include <cstdio>

#include<string.h>

using namespace std;

int max(int a,int b)

{

if(a>b)return a;else return b;

}

int main()

{

int cash,n,t,dp[100009]={0},money[200]={0},mone;

while(scanf("%d",&cash)!=EOF)

{

memset(dp,0,sizeof(dp));

scanf("%d",&n);

dp[0]=1;

int cnt=0;

for(int i=1;i<=n;i++)

{

scanf("%d%d",&t,&mone);

int k=1;

while(t-k>=0)

{

money[++cnt]=k*mone;

t-=k;

k<<=1;

}

if (t>0)money[++cnt]=t*mone;

}

for(int i=1;i<=cnt;i++)

{

for(int j=cash;j>=money[i];j--)

if (dp[j-money[i]])dp[j]=1;

}

while(dp[cash]==0)

{

cash--;

}

printf("%d\n",cash);

}

return 0;

}

巴特西

POJ 1276 Cash Machine 【DP】

最新文章

热门文章