HDU 2844 多重背包模板

HDU 2844 多重背包模板

給出n個數和m

每個數給出出現次數和價值，問任意組合組成不大於M的價值，共能產生多少個數

多重背包的的二進制優化寫法 模板mark一下

二進制優化原理：

1、2、4可以組合出所有小於8的數；
1、2、4、8可以組合出所有小於16的數；
1、2、4、8、16可以組合出所有小於32的數；
……

#include "stdio.h"
#include "string.h"

int n,m;
int dp[100010];
void complete_pack(int v)
{
    int i;
    for (i=v;i<=m;i++)
        if (dp[i-v]==1) dp[i]=1;
}

void onezero_pack(int v)
{
    int i;
    for (i=m;i>=v;i--)
        if (dp[i-v]==1) dp[i]=1;
}

void multiple_pack(int v,int c)
{
    int k;
    if (v*c>=m)
        complete_pack(v);
    else
    {
        k=1;
        while (k