首先不得不说的是dp真的很神奇（dp即动态规划，在我看来就是将最优解推到当前的一个状态转移过程，对于刚接触的小伙伴我建议手动模拟dp的过程这样才有助于理解dp）（好吧其实编程就是一个神奇的东西），对于昨晚刚学背包的我，对于2个多小时被学长灌输所有背包知识的我，现在还是有点蒙的，下面记录下我水题的记录以及各种背包模板（只记录优化之后的，如果读者有更优的代码欢迎评论区留言）

钱币兑换问题

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input

每行只有一个正整数N，N小于32768。

Output

对应每个输入，输出兑换方法数。

Sample Input

2934
12553

Sample Output

718831
13137761

解题过程：高中看到只会for超级暴力，现在感jio那时候的我特别菜（当然现在同样菜），昨天之前的我看到此题立马会想到dfs

现在的我会dp啦，下面给出代码：

​
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mm(a) memset(a,0,sizeof(a))
const int maxn=40000;
ll dp[maxn],n;
int main()
{
    mm(dp);
    dp[0]=1;//题目特判找0
    for(int i=1;i<=3;i++)//枚举1 2 3
        for(int j=i;j<maxn;j++)
            dp[j]+=dp[j-i];
    while(cin>>n)
       cout<<dp[n]<<endl;
    return 0;
}

​

Coin Change

 Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money. For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent. Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 7489 cents.

Input

The input file contains any number of lines, each one consisting of a number for the amount of money in cents.

Output

For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins. Sample Input

11 26

Sample Output

4 13

此题和钱币兑换一样只是物品不一样罢了，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mm(a) memset(a,0,sizeof(a))
const ll maxn=8000;
int w[5] = {1,5,10,25,50},W;
ll dp[maxn];
int main()
{
    while(cin>>W)
    {
        mm(dp);
        dp[0]=1;
        for(int i=0;i<5;i++)//枚举1 5 10 25 50
            for(int j=w[i]; j<=W; ++j)
                dp[j]+=dp[j-w[i]];
        cout<<dp[W]<<endl;
    }
    return 0;
}

类化的来说上面两题可以说是完全背包（即物品有无限多个）

下面是01背包的题目（01背包即物品只有一个要考虑的状态只有该物品放与不放罢了）

Bone Collector

any years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … 
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ? 

Input

The first line contain a integer T , the number of cases. 
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2 31).

Sample Input

1
5 10
1 2 3 4 5
5 4 3 2 1

Sample Output

14

此题是标准的01背包模板，但是笔者由于不够熟悉，又加之看错输入顺序折磨了我半个小时，代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mm(a) memset(a,0,sizeof(a))
const ll maxn=1500;
ll w[maxn],v[maxn],dp[maxn];
int main()
{
    int n,V,t;
    cin>>t;
    while(t--)
    {
        mm(dp);
        cin>>n>>V;
        for(int i=0;i<n;i++)//输入骨头i对应的值
            cin>>w[i];
        for(int i=0;i<n;i++)//输入对骨头i的体积
            cin>>v[i];
        for(int i=0;i<n;i++)//枚举每一种骨头
            for(int j=V;j>=v[i];j--)//到推就不会重复访问之前的状态
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        cout<<dp[V]<<endl;
    }
}

下面题是标准的完全背包，模板如下（自己理解的模板）：

湫湫系列故事——减肥记I

 

对于吃货来说，过年最幸福的事就是吃了，没有之一！ 
　　但是对于女生来说，卡路里（热量）是天敌啊！ （当然对于有些真实的吃货女生这些都不算什么的...逃）
　　资深美女湫湫深谙“胖来如山倒，胖去如抽丝”的道理，所以她希望你能帮忙制定一个食谱，能使她吃得开心的同时，不会制造太多的天敌。 

　　当然，为了方便你制作食谱，湫湫给了你每日食物清单，上面描述了当天她想吃的每种食物能带给她的幸福程度，以及会增加的卡路里量。

Input

　　输入包含多组测试用例。 
　　每组数据以一个整数n开始，表示每天的食物清单有n种食物。 
　　接下来n行，每行两个整数a和b，其中a表示这种食物可以带给湫湫的幸福值（数值越大，越幸福），b表示湫湫吃这种食物会吸收的卡路里量。 
　　最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。 

　　 [Technical Specification] 
　　1. 1 <= n <= 100 
　　2. 0 <= a,b <= 100000 
　　3. 1 <= m <= 100000 

Output

　　对每份清单，输出一个整数，即满足卡路里吸收量的同时，湫湫可获得的最大幸福值。

Sample Input

3
3 3
7 7
9 9
10
5
1 1
5 3
10 3
6 8
7 5
6

Sample Output

10
20

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000
#define mm(a) memset(a,0,sizeof(a))
int n,m,dp[maxn];
struct node
{
    int f,k;
} ans[maxn];
int main()
{
    while(cin>>n)
    {
        mm(dp);
        for(int i=1;i<=n;i++)//输入物品信息
            cin>>ans[i].f>>ans[i].k;
        cin>>m;
        for(int i=1;i<=n;i++)//枚举物品种类
            for(int j=ans[i].k;j<=m;j++)//与01背包恰好相反，完全背包正是要重复访问之前状态
                dp[j]=max(dp[j],dp[j-ans[i].k]+ans[i].f);
            cout<<dp[m]<<endl;
    }
    return 0;
}

01背包和完全背包都解释完了，那么下面就是多重背包，所谓多重背包顾明思议就是可以转化为01背包或者完全背包的一种背包类型

 

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

！灾区的食物依然短缺！ 
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。 
请问：你用有限的资金最多能采购多少公斤粮食呢？ 

后记： 
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。 
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活—— 
感谢父母，他们给予我们生命，抚养我们成人； 
感谢老师，他们授给我们知识，教我们做人 
感谢朋友，他们让我们感受到世界的温暖； 
感谢对手，他们令我们不断进取、努力。 
同样，我们也要感谢痛苦与艰辛带给我们的财富～ 

Input

输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

Output

对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

Sample Input

1
8 2
2 100 4
4 100 2

Sample Output

400

当然对于多重背包的优化就有多种了（将多数量变为多种类），笔者在此介绍自己用的方法即二进制优化，众所周知和斐波那契一样对于一个数字n，其二进制所对应的数字能组成1到n范围内的所有数，那么此题就是二进制优化最优，我写过两种二进制转化，一种是输入完物品信息，再调用自己写的函数转化，第二种是每输入完一组物品信息便转化一组，代码如下：

二进制分包函数如下：

  for(int i=0;i<n;i++){
       for(int j=1;j<=a[i].num;j<<=1){ //分解为2^x
            value[tot]=j*a[i].v;
            weight[tot]=j*a[i].w;
            tot++;
            a[i].num-=j;
        }
        if(a[i].num>0){     //最后一项补齐
            value[tot]=a[i].num*a[i].v;
            weight[tot]=a[i].num*a[i].w;
            tot++;
        }
    }

​

 按题意发挥

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000
#define mm(a) memset(a,0,sizeof(a))
int n,m,dp[maxn],top,v,w,num,t;
struct node
{
    int v,w;
} ans[maxn];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        top=1;
        for(int i=1;i<=m; i++)
        {
            cin>>v>>w>>num;
            for(int j=1; j<=num; j<<=1)//二进制转化分包
            {
                ans[top].v=v*j;
                ans[top++].w=w*j;
                num-=j;
            }
            if(num)
            {
                ans[top].v=v*num;
                ans[top++].w=w*num;
            }
        }
        mm(dp);
        for(int i=1; i<top; i++)
            for(int j=n; j>=ans[i].v; j--)
                dp[j]=max(dp[j],dp[j-ans[i].v]+ans[i].w);
        cout<<dp[n]<<endl;
    }
    return 0;
}

到此，几种背包基本类型的模板都介绍完了，希望对读者能有帮助；