首页 > 代码库 > hdu--2844--多重背包

hdu--2844--多重背包

2024-07-16 08:52:20   219人阅读

真爽啊 打完一把绝对carry的亚索 来做这题 一发AC=-=

touch  me

这题 反正数据很大 不用二进制拆分 肯定tle的

反正 二进制拆分 很简单的啊 不会的 现在看我代码 学下就好了。。

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 const int size = 100010; 6 int temp[110]; 7 int val[10010]; 8 bool dp[size]; 9 10 int main()11 {12     cin.sync_with_stdio(false);13     int i , j , n , m , cnt , num , ans;14     while( cin >> n >> m && (n||m) )15     {16         memset( dp , false , sizeof(dp) );17         ans = cnt = 0;18         for( i = 1 ; i<=n ; i++ )19         {20             cin >> temp[i];21         }22         for( i = 1 ; i<=n ; i++ )23         {24             cin >> num;25             for( j = 1 ; j<=num ; j<<=1 )26             {27                 val[cnt++] = temp[i] * j;28                 num -= j;29             }30             if( num )31                 val[cnt++] = temp[i] * num;32         }33         dp[0] = true;34         for( i = 0 ; i<cnt ; i++ )35         {36             for( j = m ; j>=val[i] ; j-- )37             {38                 if( dp[j-val[i]] )39                 {40                     dp[j] = true;41                 }42             }43         }44         for( i = 1 ; i<=m ; i++ )45         {46             if( dp[i] )47                 ans ++;48         }49         cout << ans << endl;50     }51     return 0;52 }
View Code

 


联系
我们