背包问题，除了01背包、部分背包、实数背包，更多的延展和学习可以参见当年DD大神的背包九讲
现做学习笔记如下
01背包的状态转移方程是f[i][v] = Max{f[i-1][v],f[i-1][v-w[i]]+p[i]}
该方法的空间复杂度是O(N*V),时间复杂度是O(N*V),时间复杂度基本已经不能再优化了，空间复杂度还是可以继续优化的
我们考虑该状态转移方程中任一f[i][v]只与f[i-1][1...v]相关，也就是说[1....v]这个数组是我们必须存的，因为我们不知道w[i]是多少，但是f[1....i-1]其实是不需要存的，只有f[i-1]是有用的
那么我们可不可以设计一个一维数组f[1....v]，来代表f[i-1][1.....v]呢
答案是可以的
#include <iostream>
using namespace std;
int N,V,i,j,w[101],p[101],f[101];
int main(){
cin>>N>>V;
for (i=1; i<=N; i++) cin>>p[i]>>w[i];
for (i=1; i<=N; i++){
for (j=W; j>=V; j--){
if (w[i]<=j)
f[j]= f[j-w[i]]+p[i]>f[j] ? f[j-w[i]]+p[i] : f[j];
}
}
cout<<f[N][V]<<endl;
system("pause");
return 0;
}
这段代码用一个巧妙的逆推[V.......0]，这样其实在推到主循环第i层的时候，由于j是从后往前推，所以j会用到的类似于f[j-w[i]]的值依然保存的是i-1层时候的值，相当与满足了当前递推公式中f[j-w[i]]永远拿到的是相当于原来f[i-1][j-w[i]]的值
扩展：如果将二层循环[V.....0]的逆推改成[0.....V]的正推的话，又正相当于f[j]的值是由f[i][j-w[i]]的值推算出来的，相当于完全背包问题的解决了
01背包又分两种问法：
这两种的区别只在于初始化时候的不同，必须装满的背包相当于在初始化f[0....V]的时候，除了f[0] = 0,其他f[1...V]均为-∞，这样就可以保证最终得到的f[V]是一种背包恰好被装满的状态
如果并没有要求必须装满背包，则在初始化时将f[0....V]都设置为0
这是为什么呢？可以这样理解：初始化f数组其实相当于在背包容量为[0.....V]时，没有装入任何东西时的最优解，如果是第一种情况，f[0] = 0是满足容量为0的背包被装满的情况，其他情况下背包都没有被装满，不符合要求，最大价值都是-∞，而第二种情况，因为背包允许不装满，那么初始状态下最大价值都是空背包0
这时在第一种情况，因为大家都是-∞，所以当放入物品i时，只有正好将背包装满的物品才能装入(递推公式：f[j] = max{f[j-1],f[j-w[i]]+p[i]},由于f[1.....V]都是-∞，只有w[i] == j时才可能产生装入的发生)
第二种情况是普通01背包就不用说了
与01背包不同，完全背包有N种物品和容量为V的背包，每种物品有无限多件，第i件物品的价值是p[i],体积是w[i]。求解可装入背包的最大价值
写出状态转移方程
f[i][j] = Max{f[i-1][j-k*w[i]]+p[i] | 0<=k*w[i]<=V}
因为k满足性质0<=k*w[i]<=V，可以求出每个物品最多有几件，然后将其罗列出来，变成k[i]*p[i]和k[i]*w[i]的问题
w[i]<=w[j] && p[i]>=p[j]则剪去物品j(大家都可以无限的使用了，当然优胜劣汰)w[i]>V则剪去该物品，显而易见#include <iostream>
using namespace std;
int N,V,i,j,w[101],p[101],f[101];
int main(){
cin>>N>>V;
for (i=1; i<=N; i++) cin>>p[i]>>w[i];
for (i=1; i<=N; i++){
for (j=1; j<=V; j++){
if (w[i]<=j)
f[j]= f[j-w[i]]+p[i]>f[j] ? f[j-w[i]]+p[i] : f[j];
}
}
cout<<f[N][V]<<endl;
system("pause");
return 0;
}
和01背包的代码区别只在于二层循环是从V....0还是从0.....V。
首先想想01背包为什么要逆循环？是为了保证第i次循环中，递推到f[j]的时候比j小的f[0.....j-1]存储的都是f[i-1][0....j-1]的值，换句话说，为了保证每个物品只入选一次，保证在考虑第i件物品的时候，只取决于绝无第i件物品的子集合f[i-1][0......j-1]。
而完全背包恰恰相反，当考虑加入第i件商品是，恰恰要考虑的是可能包含第i个商品的子集f[i][0......j-1]
有N种物品和容量为V的背包，第i件物品的数量为n[i]，第i件物品的价值是p[i],体积是w[i]。求解可装入背包的最大价值
与完全背包类似，将无限改成了n，状态转移方程
f[i][j] = Max{f[i-1][j-k*w[i]]+k*p[i] | 0<=k<=n[i]}
同样可以转化为01背包
因为k满足性质0<=k<=n，可以每个物品有n[i]件，然后将其罗列出来，变成n[i]*p[i]和n[i]*w[i]的问题
同样有O(VN)的解法
参考男人八题
有N种物品和容量为V的背包，第i件物品的价值是p[i],体积是w[i]。这些物品被划分为若干组，每组的物品互相冲突，只能选择一件。求解可装入背包的最大价值
相当于对每一组的物品多加了一层遍历，每一次不在选择一个物品放入与否，而是选择是否从某一组中选择一个物品放入，以及放入哪个物品
f[i][j] = Max{f[i-1][j],f[i-1][j-w[i]]+p[i] | i属于第k租}
#include <iostream>
using namespace std;
int N,V,Z,i,j,w[101],p[101],f[101],z[101];
int main(){
cin>>N>>V>>Z;
for (i=1; i<=N; i++) cin>>p[i]>>w[i]>>z[i];
for (i=1; i<=Z; i++){
for (j=1; j<=V; j++){
for (k=1; k<=N; k++){
if(z[k] != i)
continue;
if (w[k]<=j)
f[j]= f[j-w[k]]+p[k]>f[j] ? f[j-w[k]]+p[k] : f[j];
}
}
}
cout<<f[N][V]<<endl;
system("pause");
return 0;
}