004:0-1背包问题（DP）
本帖最后由 Messj 于 2018-6-8 23:34 编辑注明：本题及讲解转载自 http://blog.csdn.net/hearthougan/article/details/53869671
题目：有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 w，价值是 p。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
不妨设集合http://img.blog.csdn.net/20161225145347052?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvSGVhcnRob3VnYW4=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center表示n个物品，该问题的某一个最优解集合为http://img.blog.csdn.net/20161225152745315?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvSGVhcnRob3VnYW4=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center。
1、最优子结构
我们已经假设该问题的最优解为A，那么对于某个物品http://img.blog.csdn.net/20161225153114818?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvSGVhcnRob3VnYW4=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center，令S1=S-aj,V1=V-wj表示原问题除去物品后的一个子问题，那么,A1就是该子问题的一个最优解。可反证此问题，即存在一个A1'是子问题的最优解解，那么,所得的集合S'=A1'+aj一定比原问题最优解集合S所得的最大价值要大，这与假设矛盾。因此原问题的最优解一定包含子问题的最优解，这就证明了最优子结构性质。
2、递归地定义最优解的值
对于每个物品我们可以有两个选择，放入背包，或者不放入，有n个物品，故而我们需要做出n个选择，于是我们设f表示做出第i次选择后，所选物品放入一个容量为v的背包获得的最大价值。现在我们来找出递推公式，对于第i件物品，有两种选择，放或者不放。
<1>:如果放入第i件物品，则f = f]+p,表示，前i-1次选择后所选物品放入容量为v-w的背包所获得最大价值为f]，加上当前所选的第i个物品的价值p即为f。
<2>:如果不放入第i件物品，则有f = f,表示当不选第i件物品时，f就转化为前i-1次选择后所选物品占容量为v时的最大价值f。则:
f = max{f, f]+p}
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100;
int n,V;
int f;
int w,p;
int main()
{
while(scanf("%d%d",&n,&V))
{
if(n==0 && V==0)
break;
for(int i = 0; i <= n; ++i)
{
w = 0, p = 0;
for(int j = 0; j <= n; ++j)
{
f = 0;
}
}
for(int i=0;i<n;i++)
scanf("%d%d",&w,&p);
for(int i=1;i<=n;i++)
{
for(int v=w;v<=V;v++)
{
f = max(f,f]+p);
}
cout<<f<<endl;
}
}
}
3.优化空间复杂度
上述解法的时空复杂度皆为O(VN）。时间复杂度无法再优化，但可以优化空间复杂度到O(V).
新的f依赖 上一次的 f和上一次的f]，同理，新的f依赖 上一次的 f和上一次的f],以此类推;如果是递增顺序计算，则上一次的f]会被新的f]覆盖。如果递减，则可以看到被覆盖的数f对于下一个计算f而言，是无法造成影响的（这是由于f(v)相对于f(v-1)是超前的，即将来的可能）。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100;
int n,V;
int f;
int w,p;
int main()
{
while(scanf("%d%d",&n,&V))
{
if(n==0 && V==0)
break;
memset(f, 0, sizeof(f));
memset(w, 0, sizeof(w));
memset(p, 0, sizeof(p));
for(int i=0;i<n;i++)
scanf("%d%d",&w,&p);
for(int i=1;i<=n;i++)
{
for(int v=V;v>=w;v++)
{
f = max(f,f]+p);
}
cout<<f<<endl;
}
}
}
页:
[1]