[wikioi]装箱问题

http://wikioi.com/problem/1014/ 01背包问题是最经典的动态规划之一,这道题目甚至是这其中还简单的一种,因为价值就是本身的重量了。本来比如,w是总重量限制,v[]是每个的价值。

但一开始我都有点忘了,查找了一下又勾起了回忆。
1.它把总重量从1到w作为状态,对初学者并不是很直观的。但DP本来就是空间换时间的算法,里面经常以整数做状态,数目还既不是太大又不是太小。最终经常是n^2或n^3的复杂度。
2.01背包问题是个二维数组的DP,状态转移方程式f[i,v]=max(f[i-1,m],f[i-1,m-w[i]]+v[i])。其中f[i,m]表示前i个元素在m是重量限制时的价格最大值。f[i-1,m]表示不选择i的情况,后面是选择i的情况。
3.但注意到f[i-2,m]肯定小于f[i-1,m]所以可以只保留f[m]作为当前m为重量限制时的价格最大值,那么f[m]=max(f[m-w[i]]+v[i],f[m])。化二维为一维。
4.本人的AC程序仍然用了二维数组,下次可以简化。
5.要注意边界条件i<=v,这里最大重量是可以取到的。

可参考:http://www.cnblogs.com/fly1988happy/archive/2011/12/13/2285377.html

#include <iostream>
using namespace std; int mx[31][20005];
int w[31];
int main()
{
int v;
int n;
cin >> v;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
for (int i = 0; i <= v; i++)
for (int j = 0; j < n; j++)
{
if (j==0)
{
if (w[j] <= i)
mx[j][i] = w[j];
else
mx[j][i] = 0;
}
else
{
if (w[j] > i)
mx[j][i] = mx[j-1][i];
else
{
int v1 = mx[j-1][i]; // not take w[j]
int v2 = mx[j-1][i-w[j]]+w[j];
mx[j][i] = v1 > v2 ? v1 : v2;
}
}
}
cout << (v - mx[n-1][v]);
}

PPT:http://wenku.baidu.com/view/cf389ab069dc5022aaea00c7.html

对于资源类动态规划问题,我们可以看出,问题描述必须有一个基本要素:资源,有时这种资源可能是金钱、空间或者时间,问题就是要对这些资源如何分配,一种基本的想法是将资源应用于前i个阶段,然后考虑第i个阶段和前i-1个阶段之间的关系。
设前i个点的消耗j的资源得到的最优值,研究前i-1个点消耗的资源的最优值,利用第i个点决策转移。
状态转移方程一般可写成: fi(j) = min{ fi-1 ( k) + ui (j,k)}

上一篇:mysql 查看某个库下面某个表的所有列字段, columnName


下一篇:mysql查看被锁住的表