poj 3624 Charm Bracelet 01背包问题
题目链接：poj 3624
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即F [i, v]表示前i件物品恰放入一个容量为v 的背包可以
获得的最大价值。则其状态转移方程便是:
F [i, v] = max{F [i ? 1, v], F [i ? 1, v ? Ci ] + Wi }
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生
出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v 的背包
中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化
为一个只和前i ? 1件物品相关的问题。如果不放第i件物品,那么问题就转化
为“前i ? 1件物品放入容量为v 的背包中”,价值为F [i ? 1, v];如果放第i件物
品,那么问题就转化为“前i ? 1件物品放入剩下的容量为v ? Ci 的背包中”,
此时能获得的最大价值就是F [i ? 1, v ? Ci ]再加上通过放入第i件物品获得的价
值 Wi 。
伪代码如下:
F [0, 0..V ] = 0
for i = 1 to N
for v = Ci to V
F [i, v] = max{F [i ? 1, v], F [i ? 1, v ? Ci ] + Wi }
以上方法的时间和空间复杂度均为O(V N ),其中时间复杂度应该已经不能
再优化了,但空间复杂度却可以优化到O(V )。
先考虑上面讲的基本思路如何实现,肯定是有一个主循环i = 1..N ,每次
算出来二维数组F [i, 0..V ]的所有值。那么,如果只用一个数组F [0..V ],能不
能保证第i次循环结束后F [v]中表示的就是我们定义的状态F [i, v]呢?F [i, v]是
由F [i ? 1, v]和F [i ? 1, v ? Ci ]两个子问题递推而来,能否保证在推F [i, v]时(也
即在第i次主循环中推F [v]时)能够取用F [i ? 1, v]和F [i ? 1, v ? Ci ]的值呢?事
实上,这要求在每次主循环中我们以v = V..0的递减顺序计算F [v],这样才能保
证推F [v]时F [v ? Ci ]保存的是状态F [i ? 1, v ? Ci] 的值。伪代码如下:
F [0..V ] = 0
for i = 1 to N
for v = V to Ci
F [v] = max{F [v], F [v ? Ci ] + Wi }
其中的F [v] = max{F [v], F [v ? Ci ] + Wi }一句,恰就对应于我们原来的转移方
程,因为现在的F [v ? Ci ]就相当于原来的F [i ? 1, v ? Ci ]。如果将v 的循环顺序
从上面的逆序改成顺序的话,那么则成了F [i, v]由F [i, v ? Ci ]推导得到,与本题
意不符。
代码：
#include<stdio.h>#include<iostream>#include<string.h>#define N 3405using namespace std;int bag[12900];int w[N],d[N];int main(void){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>w[i]>>d[i]; memset(bag,0,sizeof(bag)); for(int i=1;i<=n;i++)for(int k=m;k>=w[i];k--){ if(bag[k-w[i]] + d[i] > bag[k])bag[k] = bag[k - w[i]] + d[i];} cout<<bag[m]<<endl; return 0;}