洛谷P1049 [NOIP2001 普及组] 装箱问题

本题就是一个简单的01背包问题

1.因为每个物品只能选一次，而且要使箱子的剩余空间为最小。所以可以确定属性为 MAX

2.由于是从n个物品里面选i个物品那么就是选出的i个物品的空间总和要尽可能的大

就可以得到动态规划的表达式

f[i][j] = max(f[i-1][j],f[i-1][j-w[i]] + w[i]);

就可以得到完整的代码

#include <iostream>

using namespace std;

const int N = 55 , M = 20010;

int f[M][M];

int w[N];

int n;

int v;

int main()

{

   cin >> v >> n;

   for ( int i = 1; i <= n; i++ ) cin >> w[i];

   for( int i = 1 ; i <= n ; i++ )

     for( int j = 0 ; j <= v ; j++ )

     {

         f[i][j] = f[i -1][j];

         if( j >= w[i] ) f[i][j] = max(f[i-1][j],f[i-1][j-w[i]] + w[i]);

     }

     cout << v - f[n][v];

   return 0;

}

我觉得这个还是不够好，由于此题是线性Dp所以我们用滚动数组进行优化

得到以下代码，一下就变快了不少呢

#include <iostream>

using namespace std;

const int N = 55 , M = 20010;

int f[M];

int w[N];

int n;

int v;

int main()

{

   cin >> v >> n;

   for ( int i = 1; i <= n; i++ ) cin >> w[i];

   for ( int i = 1 ; i <= n; i++ )

      for ( int j = v; j >= w[i]; j-- )

      {

         f[j] = max(f[j],f[j - w[i]] + w[i]);

      }

   cout << v - f[v];

   return 0;

}

巴特西

洛谷P1049 [NOIP2001 普及组] 装箱问题

最新文章

热门文章