完全背包问题实例
完全背包问题 （我完全是一个完全背包）
题目描述
零崎有很多朋友，其中有一个叫做lfj的接盘侠。
lfj是一个手残，他和零崎一起玩网游的时候不好好打本，天天看拍卖行，没过多久，就成为了一个出色的商人。时间一长，虽然挣了不少钱，却没时间练级了。
作为lfj的友人，零崎实在看不下去，于是他决定帮lfj一把。当然了，零崎肯定不会自己动手，活还得你们来干。
lfj可以提供给你们拍卖行所有能买到物品的价格和利润，由于游戏产出不限，所以可以假定只要有钱，即使是同一种东西，多少个也都能买到手。lfj还会告诉你他初始的成本。虽然零崎想让你们给出一次交易中利润最大的购买方案，但是lfj觉得只要知道最大利润就可以了。
输入
每组数据第一行为两个整数P和N，表示本金和拍卖行物品种类数。
接下来N行，每行两个数据pi,ci代表第i类物品的利润和购买价格。
1<=P<=20000,1<=N<=300,1<=c,p<=200
输出
对于每组数据，输出一行，为能获得的最大利润
输入样例
3 1
2 1
2 3
1 1
1 2
2 1输出样例
6
4Hint
使用if直接比较不要调用max（）以防超时
完全背包问题：
完全背包和0-1背包的不同之处：完全背包的物品不再是只有一件而是有无数件，所以对于某一件物品也不再是拿（1）不拿（0）。而是变为了拿0件，1件，2件…k件,按照0-1背包问题的状态转移方程同样可以写出完全背包的状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
分析上述的状态转移方程
这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度是超过O(VN)的。
因此我们需要对改状态方程进行改进：
O(VN)的算法：
1 for (int i = 1; i <= N; i++) 2 3 for (int v = 0; v <= V; v++) 4 5 f[v] = max(f[v], f[v - c[i]] + w[i]);
或者f[i][v]=max(f[i-1][v],f[i][v-c[i]]+w[i])
可以发现和0-1背包不同的地方只是在于内部for循环的起止改变了顺序，为什么这样可以实现完全背包的要求呢？
首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。
因此可以得到完全背包的代码实现：
1 void CompletePack(int cost , int weight) 2 { 3 for (int i = weight ; i <= W ; ++ i) 4 f[i] = max(f[i],f[i-weight]+cost) ; 5 }
下面给出本题的代码实现：
1 #include <bits/stdc++.h> 2 long long f[20010]; 3 long long c[310]; 4 long long v[310]; 5 using namespace std; 6 7 int main() 8 { 9 int V,k; 10 while(~scanf("%d%d",&V,&k)) 11 { 12 memset(f,0,sizeof(f)); 13 memset(c,0,sizeof(c)); 14 memset(v,0,sizeof(v)); 15 for(int i=1; i<=k; i++) 16 scanf("%lld%lld",&v[i],&c[i]); 17 for(int i=1; i<=k; i++) 18 { 19 for(int j=c[i]; j<=V; j++) 20 { 21 if(f[j-c[i]]+v[i]>=f[j]) 22 f[j]=f[j-c[i]]+v[i]; 23 else 24 f[j]=f[j]; 25 } 26 } 27 printf("%lld\n",f[V]); 28 } 29 }