动态规划入门-01背包问题

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 = 3500;
const int maxnw = 13000;
int dp[maxnp][maxnw];
int value[maxnp];
int weight[maxnw];
int N, M;

void output();

void solve()
{
    memset(dp,0,sizeof(dp));

    for(int i = 1 ; i <= N ; i++)
    {
        for(int j = 1 ; j < weight[i] ; j++)
            dp[i][j] = dp[i-1][j];
        for(int v = weight[i] ; v <= M ; v++)
        {
            dp[i][v] = max(dp[i-1][v],dp[i-1][v-weight[i]]+value[i]);
        }
    }
}

int main()
{
    cin >> N >> M;

    for(int i = 1 ; i <= N; i++)
    {
        cin >> weight[i] >> value[i];
    }

    solve();

    cout << dp[N][M] <<endl;
}

然后可以从上边的这个部分：

for(int j = 1 ; j < weight[i] ; j++)
            dp[i][j] = dp[i-1][j];
        for(int v = weight[i] ; v <= M ; v++)
        {
            dp[i][v] = max(dp[i-1][v],dp[i-1][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 = 3500;
const int maxnw = 13000;
int dp[maxnw];
int value[maxnp];
int weight[maxnw];
int N, M;

void solve()
{
      memset(dp,0,sizeof(dp));
      for(int i = 1; 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 = 1 ; i <= N; i++)
          {
                cin >> weight[i] >> value[i]; 
          }
          solve();
    }
    return 0;
}

这个代码可以保证不会内存超限

这个是我第一次写出dp的代码，希望以后写的越来越好