首页 > 代码库 > TYVJ1194

TYVJ1194

2024-07-19 06:56:19   216人阅读

多重背包的二进制优化
题目要求是把所有的物品分成两部分，使得两部分价值之和相等
可以先把总的价值之和m求出然后除2，(如果m是奇数，可以直接Can‘t)然后把第i种大理石分成a[i]个独立的物品，价值和费用都为i，然后把这些物品放入容量为m的背包，如果能恰好放满，则说明可以划分。
时间复杂度O(m*n)m最大为60000 n最大为20000，相乘得1.2*e9
显然会超时，需要优化。多重背包一般都需要二进制优化，这东西不想多说了，背包九讲上很详细(背包九讲真的很强大，你值得拥有！~) 完事，再用恰好装满的01背包算一下，如果dp[m]==m就can否则can‘t

背包九讲全部理解了，背包问题以后应该就不会出问题，所以继续吧。

 

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define INF 11111111 6 using namespace std; 7  8 const int maxv = 60005; 9 const int maxn = 200;10 int a[7],s[maxn],dp[maxv];11 int main()12 {13     //freopen("in.txt","r",stdin);14     int m,n;15     while(1)16     {17         int m = 0,cnt = 1;18         for(int i = 1;i<=6;++i)19         {20             cin>>a[i];21             m = m+a[i]*i;22 23             int k = 1;24             while(a[i]>=k)25             {26                 s[cnt++] = k*i;27                 a[i]-=k;28                 k*=2;29             }30             if(a[i])s[cnt++] = a[i]*i;31 32         }33         dp[0] = 0;34         if(!m)return 0;35         if(m%2){printf("Can‘t\n");continue;}36         m/=2;37         for(int i = 1;i<cnt;++i)38         {39             dp[i] = -INF;40             for(int j = m;j>=s[i];--j)41                 dp[j]=max(dp[j],dp[j-s[i]]+s[i]);42         }43         if(dp[m]==m)printf("Can\n");44         else printf("Can‘t\n");45     }46     return 0;47 }

 

TYVJ1194


联系
我们