1.引言
能用背包问题解决的一类问题有一个特点，一个背包，若干物品，物品必须有两个属性：价值（c）和体积（w）。只有一个属性的物品是不能用背包问题来解决的！！！
背包问题是一个DP，背包的状态就是DP的状态，背包问题有一个非常重要的递推公式：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
可以这样理解：对于第i件物品的决策有两种，放（必须要有足够容量）或者不放。不放f[i][v]即为前i-1种物品的子问题，此时背包可用容量不变；如果放入第i件物品，则f[i][v]为前i-1件物品的子问题加上第i件物品价值，并且背包可用容量减少第i件物品的体积数。
2.0-1背包
以HDOJ-2602为例来说明：
Many 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 ?
输入说明
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.
输出说明
One integer per line representing the maximum of the total value (this number will be less than 231).
输入样例
1
5 10
1 2 3 4 5
5 4 3 2 1
输出样例
14
规划过程如下：
因为是0-1背包问题，每一件物品最多只能放入一件，所以为了避免放入多件必须从后向前遍历。伪代码如下：
for i = 1 to n //所有物品
for j = V to v[i]
dp[j] = max(dp[j] , dp[j-v[i]] + w[i]);
这样空间复杂度是O(nV)，可以将空间复杂度降低为O（V）。因为第i件物品的决策是建立在前i-1件物品的子问题上的。将状态转移方程改为：
f[v]=max{f[v],f[v-c[i]+w[i]}
就可以重复利用数组。
该题的源代码：
#include <iostream>
using namespace std;
int value[1001];
int volum[1001];
int dp[1001];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int row;
int numbers,volum_sum;
int i,v;
cin >> row;
while(row!=0)
{
cin >> numbers >> volum_sum;
for (i=1;i<=numbers;i++)
cin>>value[i];
for (i=1;i<=numbers;i++)
cin>>volum[i];
for (i=0;i<=volum_sum;i++)
dp[i]=0;
for (i=1;i<=numbers;i++) //numbers件物品
for (v=volum_sum;v>=volum[i];v--)//0不需判定
dp[v]=max(dp[v-volum[i]]+value[i],dp[v]);
cout << dp[volum_sum]<<endl;
row--;
}
return 0;
}
3.完全背包问题
完全背包问题是指，所有的物品都有无限件，可以放入任意件数。由0-1背包问题的原始状态转移方程可以得到完全背包问题的状态转移方程为
f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}
意思是指第i件物品放入若干件就减去响应若干件的体积，或者一件不放。对于程序实现上来说，放入多少件物品并不需要进行循环。相对与0-1背包问题，将循环从后遍历改为从前遍历就可以了。伪代码：
for i = 1 to n //所有物品
for j = v[i] to V
dp[j] = max(dp[j] , dp[j-v[i]] + w[i]);
3.1完全背包例题：HDOJ 1114 - Piggy-Bank
问题描述
Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM).
The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time,
there should be enough cash in the piggy-bank to pay everything that needs to be paid. But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there
is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights
of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely
broken pigs!
输入说明
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F.
They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500)
that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units,
W is it's weight in grams.
输出说明
Print exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount
of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.".
输入样例
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
输出样例
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.
这一题是求最小的值，和背包问题的最大值相反，所以修改公式就可以了，但是此时的初始值必须定义为一个无穷大值！！！！！
#include<iostream>//简单DP（动态规划）
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int MAX=501;
const int Max=50001;
const int maxn=9999999;
int DP[Max];
typedef struct piggy_bank//定义存钱罐
{
int value;
int weight;
}bank;
bank s[MAX];
int main()
{
int t,e,f,n,i,j,sub;
cin>>t;
while(t--)
{
cin>>e>>f;
sub=f-e;//实罐与空罐的重量之差，表示可以装的钱最大重量
cin>>n;
for(i=0;i<n;i++)
cin>>s[i].value>>s[i].weight;
DP[0]=0;
for(j=1;j<=sub;j++)//初始化
DP[j]=maxn;
for(i=0;i<n;i++)
{
for(j=s[i].weight;j<=sub;j++)
{
if(DP[j-s[i].weight]+s[i].value<DP[j])//简单DP
DP[j]=DP[j-s[i].weight]+s[i].value;
}
}
if(DP[sub]==maxn)//如果不可能
cout<<"This is impossible."<<endl;
else
cout<<"The minimum amount of money in the piggy-bank is "<<DP[sub]<<'.'<<endl;
}
return 0;
}