HDU 2844 Coins(多重背包)

?

现在有价值val[1],val[2],…val[n]的n种硬币, 它们的数量分别为num[i]个. 然后给你一个m, 问你区间[1,m]内的所有数目, 由之前n种硬币来构造(即选取某些硬币使得这些硬币的价值和等于[1,m]区间的特定数), 最多能构造出这m个数中的多少个?

分析:

基本的完全背包问题.

我们令dp[i][j]==x表示用前i种硬币且硬币总价值总价值正好等于j时, 有多少种方法.

初始化: dp为全0,且 dp[0][0]==1.

对于每种硬币, 我们有两种可能的方式处理:

1. Val[i]*num[i]>= m时, 对当前硬币做一次完全背包即可.

2. Val[i]*num[i]

1个 2个 4个… 2^(k-1)个, 以及 num[i]-2^k+1个

然后我们对上面k+1类物品每个都做一次01背包即可, 因为对上面k+1类新物品的01选择会覆盖我们所有可能的对原来第i类物品做的任何选择.

最终所求: 所有使得dp[n][j]!=0 的j值得和. (1<=j<=m)

AC代码:

?

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=100000+5; int n;//物品种数 int m;//总金钱数 int cost[100+5];//第i种物品的花费 int num[100+5]; //第i种物品的数量 int dp[maxn]; //1次01背包过程 void ZERO_ONE_PACK(int cost) { for(int i=m;i>=cost;i--) dp[i] += dp[i-cost]; } //1次完全背包过程 void COMPLETE_PACK(int cost) { for(int i=cost;i<=m;i++) dp[i] += dp[i-cost]; } //1次多重背包过程 void MULTIPLY_PACK(int cost,int num) { if(cost*num>=m) { COMPLETE_PACK(cost); return ; } int k=1; while(k
     
      
?