First：0-1背包问题

1.定义define：

所谓的0-1背包就是指每种物品只有一件，而每件物品只有两种选择，即选择放或是不放

2.问题：

一个小偷来出来活动了， 拿了一个背包， 最多可以装50斤的东西的小袋子。 他眼睛一亮， 发现了三件宝贝a, b, c.   其中a重10斤， 价值60元; b重20斤， 价值100元; c重30斤， 价值120元。 问： 在背包允许的范围内， 小偷最多能偷到多少钱？简单的说就是现有N种物品和重量为V的背包，第i件物品的重量为c[i]，价值为w[i]，求解将哪些物品放入背包可使价值总和达到最大。

3.思路：

在背包所能承受的最大容量下得到最大价值 

子问题状态:f[ j ]的含义：表示前i件物品放入容量为j的背包的情况下价值的最优解

状态转移方程：f[j] = max{f[j],f[j - weight[i]] + value[i]} 

初始化：（因为f 数组中存的是前i件物品放入j容量的背包的最大价值）f数组初始值定义为0

4.code精华：

for(i=0;i<N;i++)
{
    for(j=V;j>=weight[i];j--)
        f[j]=max(f[j],f[j-weight[i]]+value[i]);

}

我们可以顺着这个for循环一起走两趟，设N=3，V=5，weight[N]=｛1，2，3｝，value[N]=｛6，10，10｝，一开始背包里没有装任何物品，所以一开始初始值f[0]=f[1]=f[2]=f[3]=f[4]=f[5]=0;接下来我们一起走循环，

5.完整代码：

#include <bits/stdc++.h>
    using namespace std;
    int n,v,weight[5],value[5],f[10];
    int ZeroOnePack()
    {
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++)
        {
            for(int j=v;j>=weight[i];j--)
            {
                f[j]=max(f[j],f[j-weight[i]]+value[i]);
                cout<<j<<" "<<f[j]<<endl;
            }
        }
        return f[v];
    }
    int main()
    {
        int t;
        cin>>n>>v;
        for(int i=0;i<n;i++)
            cin>>weight[i];
        for(int i=0;i<n;i++)
            cin>>value[i];
        t=ZeroOnePack();
        cout<<t<<endl;

        return 0;

   }

Second：完全背包问题

1.定义：

完全背包和0-1背包最大的区别就是完全背包中每种物品有无限个，即在不超过背包容量下，可以拿多个价值一样大的物品。

2.code精华：

int CompletePack()
{
    memset(f,0,sizeof(f));
    for(i=0;i<n;i++)
    {
            for(j=weight[i];j<=v;j++)
            {
                f[j]=max(f[j],f[j-weight[i]]+value[i]);
                cout<<j<<" "<<f[j]<<endl;
            }
    }
    return f[v];

}

其他的和0-1背包是类似的，可以对比着看看

3.例题：http://poj.org/problem?id=1384（Piggy-Bank）

题意：现有一个小猪存钱罐，里面存有不同种类的硬币，求在不打碎小猪的情况下，算出存钱罐中最少有多少钱。给出空小猪的重量、小猪和硬币的总重量、每种硬币单个的价值和重量，输出给定总重量的硬币可以实现的最小金额，如果无法准确达到重量，就输出“这是不可能的”。

Sample  Input：

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Sample  Output：

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

思路：这里求的是最小值，但其实万变不离其中，它的动态转移方程为：dp[j]=min(dp[j],dp[j-w[i]]+v[i]);

My  Code：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9;
int main()
{
    int t,n,E,F,v[505],w[505],f[10005];
    cin >> t;
    while(t--)
    {
        cin >> E >> F;
        int W = F-E;
        for(int i = 0; i <= W; i++) f[i] = INF;///要求最小值，初始化为无穷大
        cin >> n;
        f[0] = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> v[i] >> w[i];
            for(int j = w[i]; j <= W; j++)
                f[j] = min(f[j],f[j-w[i]]+v[i]);
        }
        if(f[W] == INF)///如果硬币总重量的价值还是初始值的话，则说明无法达到准确重量
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n",f[W]);
    }
}

总结：（0-1背包与完全背包的比较）

       假设求容量 j 的最大价值 f [ j ]，f[ j ] = max( f [ j ], f [ j-weight[i] ]  + value[i] )，由于完全背包中物件有无限个，那么 f [ j-weight[i] ]中可能已经取过物件 i 了，因此for循环是正着走的，因为它可以一直取同一个物件，最终求出满足容量的最大价值；而0-1背包每个物件只有一个，它的f [ j-weight[i] ]中一定没取物件 i ，因此for循环是倒着走的，以防多取了同一个物件。