参考链接：
1.背包问题详解：01背包、完全背包、多重背包
2.九种背包问题，让你永恒拥有背包算法（贪心）
1. 01背包问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
优化空间复杂度
f[v]=max{f[v],f[v-c[i]]+w[i]};
v 代表背包的容量，f[v]代表背包容量为v时可以获得的最大价值，在取不取第i个问题上，不取就是f[v]，取就是f[v-c[i]]+w[i]。
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
例题 我需要一个优惠！
Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。
输入输入有若干组数据，每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000) 后面的m行，每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。 输入的最后有两个0。 产量每组数据都对应一个输出，表示Speakless可能得到至少一份offer的最大概率。用百分数表示，精确到小数点后一位。 样本输入
10 3 4 0.1 4 0.2 5 0.3 0 0样本输出
44.0%分析：要求最大概率，最大概率=1-（1-p1）(1-p2)...(1-pn);因此只要求这些乘积的最小值
#include<stdio.h> #include<iostream> using namespace std; int main() { int n,T,t[10001],i,j; float v[10001]; float s[100000]; while(scanf("%d%d",&T,&n)!=EOF) { if(T==0&&n==0) break; for(int o=0;o<1000;o++) { s[o]=1; } for(i=0;i<n;i++){ scanf("%d%f",&t[i],&v[i]); v[i]=1-v[i]; } for(i=0;i<n;i++) { for(j=T;j>=t[i];j--) { if(s[j]>s[j-t[i]]*v[i]) s[j]=s[j-t[i]]*v[i]; } } float u=100-s[T]*100; printf("%.1f%%\n",u); } return 0; }
2.完全背包问题
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
同样，空间优化，
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
3.多重背包问题
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本算法 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取 n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f[i][v]=max{f[i-1][v-k*c[i]]+ k*w[i]|0<=k<=n[i]}。复杂度是O(V*∑n[i])。 转化为01背包问题 另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为∑n[i]的01背包问题，直接求解，复杂度仍然是O(V*∑n[i])。
多重背包就相当于01背包中又加了一层循环，即每件物品的个数，如果个数较小时，可以直接接一层循环，但是如果个数较多时，可以将个数转化为二进制数优化。
例题 HDU中的重大事件
如今，我们都知道计算机学院是HDU最大的部门。但是，也许你不知道2002年计算机学院曾被分成计算机学院和软件学院。 分裂绝对是HDU中的一件大事！与此同时，这也是一件麻烦事。所有设施必须减半。首先，评估所有设施，如果它们具有相同的值，则认为两个设施是相同的。假设有N（0 <N <1000）种设施（不同的值，不同的种类）。
输入输入包含多个测试用例。每个测试用例以数字N开始（0 <N <= 50 - 不同设施的总数）。接下来的N行包含整数V（0 <V <= 50 - 设施值）和整数M（0 <M <= 100 - 相应的设施数）。您可以假设所有V都不同。 以负整数开头的测试用例终止输入，并且不处理该测试用例。 产量对于每种情况，打印一行包含两个整数A和B，分别表示计算机学院和软件学院的价值。A和B应尽可能相等。同时，你应该保证A不低于B. 样本输入
2 10 1 20 1 3 10 1 20 2 30 1 -1样本输出
20 10 40 40
分析：背包的容量即为sum（设施数量*设施的值），但是不同的设施有不同的数量，我在做此多重背包问题上，将其转化为01背包问题。
代码如下：
#include <iostream> #include<stdio.h> using namespace std; int main() { int n; int j; int value[50]; int number[50]; int numbers; int sum; int bag; int i; while(scanf("%d",&n)!=EOF) { if(n<0) break; sum=0; numbers=0; int vol[100000]={0}; int s[100000]={0}; for( i=0;i<n;i++) { scanf("%d%d",&value[i],&number[i]); sum=sum+number[i]*value[i]; numbers=numbers+number[i]; } int k=0; bag=sum/2; for(i=0;i<n;i++) for(j=0;j<number[i];j++) { vol[k]=value[i]; k++; } for(i=0;i<numbers;i++) { for(j=bag;j>=vol[i];j--) { if(s[j]<s[j-vol[i]]+vol[i]) s[j]=s[j-vol[i]]+vol[i]; } } printf("%d %d\n",sum-s[bag],s[bag]); } return 0; }
