Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf 【动态规划】0-1背包-白红宇

Codeforces Round #178 (Div. 2) B. Shaass and Bookshelf 【动态规划】0-1背包

阅读量：5338 次

发布时间：2019-06-15

本文共 2476 字，大约阅读时间需要 8 分钟。

0-1背包（数组开小贡献了4个wa）

原理解释：

这是一个0-1背包模型

如果想对背包问题有更深入的理解可以看这里：

或上百度查“背包问题九讲”。

现在按我的方法来解释一下（最基本的开二维数组的）0-1背包：

0-1背包问题原型：现在我有一个容量为V的空背包，而现在我在某个地下城堡里发现了n颗珍贵的宝石，每颗宝石i都有他的体积cost[i]和价值value[i]。于是我要找到最好的一种方式在背包容量有限的情况下装进一些宝石使得他们的总价值最高。

设数组dp[i][j]表示当现在背包里装进总体积为i的一些宝石时能获得价值j的情况是否存在，dp[i][j]=1表示存在,dp[i][j]=0表示不存在。于是：

最初（n个宝石都没有放进去的时候）:

只有：dp[0][0] = 1;(表示背包里面放进0块宝石时获得0价值的情况存在)

其他全等于0.

然后考虑放不放第1块宝石：

有：dp[0][0] = 1 ; (表示背包里面放进0块宝石时获得0价值的情况存在)

dp[cost[1]][value[1]] = 1;(表示背包里面放进宝石1时占用体积cost[1]获得价值value[1]的情况存在)

其他全等于0.

然后考虑放不放第2块宝石：

有：dp[0][0] = 1 ; (表示背包里面放进0块宝石时获得0价值的情况存在)

dp[cost[1]][value[1]] = 1;(表示背包里面放进宝石1时占用体积cost[1]获得价值value[1]的情况存在)

dp[cost[2]][value[2]] = 1;(表示背包里面放进宝石2时占用体积cost[2]获得价值value[2]的情况存在)

dp[cost[1]+cost[2]][value[1]+value[2]]=1;(表示背包里面放进宝石1和2时占用体积cost[1]+cost[2]获得价值value[1]+value[2]的情况存在)

其他全等于0.

......

然后这个dp[][]数组就记录了所有的情况。

在这道题中，我同样开了一个dp[][]数组，将thickness抽象成每一颗宝石的体积，将width抽象成每一颗宝石的价值，那么这里dp[i][j]的意思就是说当我取出thickness为i的书本的时候能不能够堆出厚度j，如果存在这样的情况dp[i][j]=1。

因为我们要求的是最小的剩余thickness，假设总的thickness为tot，i=tot-thickness,那么我们就是要找到最大的i使得存在j<=tot-i,使得dp[i][j] = 1（我在这里进行了一下处理，即如果dp[i][j-1]=1,那么dp[i][j]也=1,这样我只要判断dp[i][tot-i]是不是等于1就行了），这一步可以用二分，但是因为总的thickness也不过200，所以我这里是用的枚举。

我能想到的最好的优化是用一维的背包加二分做，不过在当时的那种情况下还是用了上述的二维空间的背包加枚举了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              using namespace std;template 
              
                void checkmin(T &t,T x) { if(x < t) t = x;}template 
               
                 void checkmax(T &t,T x) { if(x > t) t = x;}template 
                
                  void _checkmin(T &t,T x) { if(t==-1) t = x; if(x < t) t = x;}template 
                 
                   void _checkmax(T &t,T x) { if(t==-1) t = x; if(x > t) t = x;}typedef pair 
                  
                    PII;typedef pair 
                   
                     PDD;typedef long long ll;#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++)int n;const int N = 2200 , M = 10100;int tt , ww;bool dp[N][M];int t[N] , w[N];void sss(int t,int w) { for(int i=tt;i>=t;i--) for(int j=ww;j>=w;j--) if(dp[i-t][j-w]) dp[i][j] = 1;}void solve() { dp[0][0] = 1; for(int i=0;i
                    
                     =1;i--) { for(int j=1;j<=tt;j++) { if(dp[i][j]) { for(int k=j+1;k<=tt;k++) dp[i][k] = 1; break; } } }}int main() { cin >> n; tt = ww = 0; for(int i=0;i
                     
                      > t[i] >> w[i] , tt += t[i] , ww += w[i]; solve(); after(); int ans = tt; //cout << dp[2][1] << endl; for(int i=tt-1;i>=0;i--) if(dp[tt-i][i]) ans = i; cout << ans << endl; return 0;}

转载于:https://www.cnblogs.com/aiiYuu/archive/2013/04/08/3006591.html

你可能感兴趣的文章