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
