2017-08-12 18:50:13
writer：pprp
对于最基础的动态规划01背包问题，都花了我好长时间去理解；
poj3624是一个最基本的01背包问题：
题意：给你N个物品，给你一个容量为M的背包
给你每个物品的重量，Wi
给你每个物品的价值，Di
求解在该容量下的物品最高价值？
分析：
状态：
dp[i][j] = a 剩下i件 当前容量为j的情况下的最大价值为a
如果用 i 来枚举物品编号， 用 j 来枚举重量，那么
if ( j is from 1 to weight[i] ) dp[i][j] = dp[i-1][j];
if( j is from weight[i] to M) dp[i][j] = max{ dp[i-1][j] , dp[i-1][j - weight[i]] + value[i]}
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<stack> using namespace std; const int maxnp = ;
const int maxnw = ;
int dp[maxnp][maxnw];
int value[maxnp];
int weight[maxnw];
int N, M; void output(); void solve()
{
memset(dp,,sizeof(dp)); for(int i = ; i <= N ; i++)
{
for(int j = ; j < weight[i] ; j++)
dp[i][j] = dp[i-][j];
for(int v = weight[i] ; v <= M ; v++)
{
dp[i][v] = max(dp[i-][v],dp[i-][v-weight[i]]+value[i]);
}
}
} int main()
{
cin >> N >> M; for(int i = ; i <= N; i++)
{
cin >> weight[i] >> value[i];
} solve(); cout << dp[N][M] <<endl;
}
然后可以从上边的这个部分：
for(int j = ; j < weight[i] ; j++)
dp[i][j] = dp[i-][j];
for(int v = weight[i] ; v <= M ; v++)
{
dp[i][v] = max(dp[i-][v],dp[i-][v-weight[i]]+value[i]);
}
看出来有点冗余复杂,出现了MLE
现在重新定义一个状态：dp[i]表示重量剩余 i 的时候可以得到的最大价值
状态转移：dp[i] = max(dp[i], dp[i-weigth[j]]+value[j]);
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<stack> using namespace std; const int maxnp = ;
const int maxnw = ;
int dp[maxnw];
int value[maxnp];
int weight[maxnw];
int N, M; void solve()
{
memset(dp,,sizeof(dp));
for(int i = ; i <= N; i++)
{
for(int j = M ; j >= weight[i] ; j--)
{
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
}
}
cout << dp[M] << endl;
} int main()
{
while(cin >> N >> M)
{
for(int i = ; i <= N; i++)
{
cin >> weight[i] >> value[i];
}
solve();
}
return ;
}
这个代码可以保证不会内存超限
这个是我第一次写出dp的代码，希望以后写的越来越好