转载请注明出处：http://blog.csdn.net/u012860063

贴一个自觉得解说不错的链接：http://www.cppblog.com/tanky-woo/archive/2010/07/31/121803.html

模版就直接贴代码：

01背包模板：

/*

01背包问题

01背包问题的特点是，">每种物品仅有一件。能够选择放或不放。

01背包问题描写叙述：

有N件物品和一个容量为V的背包。

第i件物品的重量是c[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

*/

#include <stdio.h>

#define N 1050017

int max(int x,int y)

{

	int M;

	M=x>y ?

x : y;

	return M;

}

int wei[N],val[N],f[N];

int main()

{

	int i, j, n, m;

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

	{

		scanf("%d", &m);

		for(i=0; i<n; i++)

			scanf("%d%d", &wei[i],&val[i]);//wei[i]为重量，val[i]为价值

		for(i=0; i<n; i++)

		{

			for(j=m; j>=wei[i]; j--)

				f[j] = max(f[j], f[j-wei[i]]+val[i]);

		}

		printf("%d\n",f[m]);

	}

	return 0;

}

//此代码为poj3624

全然背包模板：

/*

全然背包问题的特点是，每种物品能够无限制的反复使用。能够选择放或不放。

全然背包问题描写叙述：

有N物品和一个容量为V的背包。第i件物品的重量是wei[i]，价值是val[i]。

*/

#include <cstdio>

#define INF 0x3fffffff

#define N 10047

int f[N],val[N],wei[N];

int min(int a,int b)

{

	if(a < b)

		return a;

	return b;

}

int main()

{

	int t,i,j,k,E,F,m,n;

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%d",&E,&F);

		int c = F-E;

		for(i = 0 ; i <= c ; i++)

			f[i]=INF;

		scanf("%d",&n);

		for(i = 0 ; i < n ; i++)

		{

			scanf("%d%d",&val[i],&wei[i]);//val[i]为面额。wei[i]为重量

		}

		f[0]=0;//由于此处如果的是小猪储钱罐 恰好装满 的情况

		//注意初始化（要求恰好装满背包，那么在初始化时除了f[0]为0其他f[1..V]均设为-∞。

		//这样就能够保证终于得到的f[N]是一种恰好装满背包的最优解。

		//如果并没有要求必须把背包装满。而是仅仅希望价格尽量大，初始化时应该将f[0..V]所有设为0）

		for(i =0 ; i < n ; i++)

		{

			for(j = wei[i] ; j <= c ; j++)

			{

				f[j] = min(f[j],f[j-wei[i]]+val[i]);//此处求的是最坏的情况所以用min。确定最少的钱,当然最后就用max了。HEHE

			}

		}

		if(f[c] == INF)

			printf("This is impossible.\n");

		else

			printf("The minimum amount of money in the piggy-bank is %d.\n",f[c]);

	}

	return 0;

}

//此代码为HDU1114;

    f[w] 即为所求  

        初始化分两种情况：

        1、假设背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;  

        2、假设不须要正好装满 f[0~v] = 0;

多重背包模板：

//多重背包(MultiplePack): 有N种物品和一个容量为V的背包。

//第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。

//求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，

//且价值总和最大。

//HDU 2191

#include <cstdio>

#include <cstring>

#define N 247

int max(int a,int b)

{

    if(a > b)

        return a;

    else return b;

}

int main()

{

    int t,n,m,i,j,k;

    int w[N],pri[N],num[N],f[N];

    while(~scanf("%d",&t))

    {

        while(t--)

        {

            memset(f,0,sizeof(f));

            scanf("%d%d",&n,&m);//n为总金额，m为大米种类

            for(i = 0 ; i < m ; i++)

            {

                scanf("%d%d%d",&pri[i],&w[i],&num[i]);//num[i]为每种大米的袋数

            }

            for(i = 0 ; i < m ; i++)

            {

                for(k = 0 ; k < num[i] ; k++)

                {

                    for(j = n ; j >= pri[i]; j--)

                    {

                        f[j] = max(f[j],f[j-pri[i]]+w[i]);

                    }

                }

            }

            printf("%d\n",f[n]);

        }

    }

    return 0;

}