|
完全背包和多重背包。有了基本的0-1背包基础，下面的东西也就好理解了。 完全背包，指每个物品有无限多个。 多重背包，指每个物品的数量是有限的。当然，这时的问题不再是拿与不拿，而是拿多少的问题，当然不能超过背包容量。 状态转换方程： - dp( i,j ) = Max( dp( i-1, j ), dp( i-1, j-k*w[i]) + k*v[i] ) ( 0 <= k <= c/ w[i] )
编码实现： 如果直接编码，用三层循环，往往会超时。这样有一种很有效的压缩方式：二进制压缩。把原来的物品按照2的n次方进行重新组合。用1、2、4、8…进行组合，可以组合出任意的数字。POJ题目：1276 POJ3624 - #include <iostream>
- using namespace std;
- //***********************常量定义*****************************
- const int MAX_NUM = 3500;
- const int MAX_WEIGHT = 14000;
- //*********************自定义数据结构*************************
- //********************题目描述中的变量************************
- int weight[MAX_NUM];
- int value[MAX_NUM];
- //**********************算法中的变量**************************
- //进行空间压缩，使用一维数组
- int dp[MAX_WEIGHT];
- //***********************算法实现*****************************
- void Solve( int n, int w )
- {
- for( int i=1; i<=n; i++ )
- {
- //因为使用了一维数组，所有j要按照递减顺序
- for( int j=w; j>=weight[i]; j-- )
- {
- if( dp[j-weight[i]] + value[i] > dp[j] )
- dp[j] = dp[j-weight[i]] + value[i];
- }
- }
- cout << dp[w] << endl;
- }
- //************************main函数****************************
- int main()
- {
- //freopen( "in.txt", "r", stdin );
- int n, w;
- cin >> n >> w;
- for( int i=1; i<=n; i++ )
- {
- cin >> weight[i] >> value[i];
- }
- Solve( n, w );
-
- return 0;
- }
POJ1276 - #include <iostream>
- using namespace std;
- //***********************常量定义*****************************
- const int MAX_NUM = 1005;
- const int MAX_CASH_REQUEST = 100005;
- //*********************自定义数据结构*************************
- //********************题目描述中的变量************************
- int cashRequest;
- int cashKind;
- //**********************算法中的变量**************************
- //dp[i][j]表示前i个物件，cashRequest == j时，所能获得的最大金额
- int dp[MAX_CASH_REQUEST];
- //使用二进制压缩，形成的新物件
- int cnt;
- int value[MAX_NUM];
- //***********************算法实现*****************************
- void Solve()
- {
- //采用0-1背包求解
- for( int i=1; i<=cnt; i++ )
- {
- for( int j=cashRequest; j>=value[i]; j-- )
- {
- dp[j] = dp[j] > dp[j-value[i]] + value[i] ? dp[j] : dp[j-value[i]] + value[i];
- }
- }
- cout << dp[cashRequest] << endl;
- }
- //************************main函数****************************
- int main()
- {
- //freopen( "in.txt", "r", stdin );
-
- while( cin >> cashRequest >> cashKind )
- {
- //输入
- for( int i=1; i<=cashKind; i++ )
- {
- int num, deno;
- cin >> num >> deno;
-
- //二进制压缩
- for( int j=1; j<=num; j*=2 )
- {
- value[++cnt] = deno * j;
- num -= j;
- }
- if( num > 0 ) value[++cnt] = num * deno;
- }
- //处理
- Solve();
-
- //清空全局变量
- cnt = 0;
- memset( value, 0, sizeof(value) );
- memset( dp, 0, sizeof(dp) );
- }
- return 0;
- }
| 
楼主
