hiho一下第195周《奖券兑换》题目分析

10
0

《奖券兑换》题目分析

这道题一眼看去是个01背包问题。但是N和M范围都在10万，O(NM)的DP没办法在时限内出解。

进一步分析我们可以发现Wi和Pi的范围都很小，在10以内，所有本质上不同的奖品最多有100种，每种物品可能有很多件。

于是这道题又变成了一道多重背包问题。不过多重背包如果直接DP仍然是O(NM)的。这里我们介绍一种"二进制分解"的优化方法。

这种优化的思想是这样的：假设我有100件费用是W、价值的P的物品(用(W, P)表示)，意味着最优解可能从中选取0~100件。现在我把这100件(W, P)换成：

1) 1件(W, P)
2) 1件(2W, 2P)
3) 1件(4W, 4P)
4) 1件(8W, 8P)
5) 1件(16W, 16P)
6) 1件(32W, 32P)
7) 1件(37W， 37P)

一种7件物品。我们可以发现，假设最优解选择了K件(W, P)，无论K是多少，都可以通过选择以上7件中的若干件使得总费用和总价值也是(KW, KP)。换句话说，与最优解等价。反之，无论从7件中选取哪种组合，也都有一个K(0 <= K <= 100)与之对应，使得选择K件(W, P)的总费用和总价值与这种组合等价。

于是我们把100件相同的物品的背包，等价变成了7件不相同物品的背包。

具体来说，就是：假设有C件(W, P)，我们把C拆成尽可能多的2的幂之和以及剩余不足下一个2的幂的部分R，即C=1+2+4+8+...+2^K+R，其中R < 2^(K+1)。

我们用(W, P), (2W, 2P), (4W, 4P), ... (2^KW, 2^KP), (RW， RP)这K+2个物品代替原C个物品，新的背包问题与原问题是等价的。

将每种物品都做相同的二进制分解之后，对所有分解后得到的物品做01背包。

由于我们是把同类的C件物品分解成了O(logC)件物品。所以最大数据100种，总计10万件物品最多被分解成大约1000件物品。

使用01背包的DP，复杂度O(1000M)。

BTW多重背包还有一种使用单调队列优化的方法。大家感兴趣可以搜索相关的资料。

3 answer(s)

0 
/*莫名的在25分的时候WA了,我找不到自己的毛病啊,答主可以看看我的是哪儿有问题吗*/
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <set>
#include <map>
#include <queue>
using namespace std;

typedef pair<int,int> pa;
typedef long long ll;
const int inf=(1<<30);
const int maxn=100005;


void solve(){
    int n,m;
    scanf("%d%d",&n,&m);
    int a[11][11],t1,t2;
    for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) a[i][j]=0;
    for(int i=0;i<n;i++){
        scanf("%d%d",&t1,&t2);
        a[t1][t2]++;
    }
    int w[n],v[n],num=0; 
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            int temp=a[i][j];
            if(temp){
                while(temp){
                    int t=temp&-temp;
                    w[num]=t*i;
                    v[num]=t*j;
                    num++;
                    temp-=t;
                }
            }
        }
    }
    int dp[m+1];
    for(int i=0;i<=m;i++) dp[i]=0;
    for(int i=0;i<num;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);  
    printf("%d",dp[m]);
}

int main(){
    solve();
    return 0;
}

  • 你这个划分的方法错了 不是把C的二进制数拆出来 而是拆成2^0,2^1,..,2^k,C-2^(k+1)+1,这样拆的意思是小于等于C的任意数字都能通过这种方式组合起来因而和C等价，像你这样把C的二进制拆出来的物品和C个物品不等价。

  • 确实,我没有理解到他的解法的精髓,谢谢了,搞懂了

  • 添加评论
  • ✖reply
1

/莫名的在25分的时候WA了,我找不到自己的毛病啊,答主可以看看我的是哪儿有问题吗/

include

include

include

include

include

include

include

include

include

using namespace std;

typedef pair pa; typedef long long ll; const int inf=(1<<30); const int maxn=100005;

void solve(){ int n,m; scanf("%d%d",&n,&m); int a[11][11],t1,t2; for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) a[i][j]=0; for(int i=0;i=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d",dp[m]); }

int main(){ solve(); return 0; }

0

牛掰，一看题目就觉得是01背包，提交超时，就没辙了。

write answer 切换为英文 切换为中文

转发分享

▲