[POJ 2754] Similarity of necklaces 2【多重背包+二进制优化】

  • 2018-01-25
  • 0
  • 0

Problem:

Time Limit: 2000MS Memory Limit: 65536K

Description

The background knowledge of this problem comes from "Similarity of necklaces". Do not worry. I will bring you all the information you need.

The little cat thinks about the problem he met again, and turns that problem into a fair new one, by putting N * (N + 1) / 2 elements into a linear list, with M = N * (N + 1) / 2 elements:

(The above table denotes Table and Pairs in description of after converting)

One more array named "Multi" appears here. Suppose Pairs and Multi are given, the little cat's purpose is to determine an array Table with M integers that obey:

(this condition is similar with the condition

that appears in the problem "Similarity of necklaces") and make

as large as possible. What is more, we must have Low[i] <= Table[i] <= Up[i] for any 1 <= i <= M. Here Low and Up are two more arrays with M integers given to you.

Input

The input contains a number of test cases. Each of the following blocks denotes a single test case. A test case starts by an integer M (1 <= M <= 200) and M lines followed. The i-th line followed contains four integers: Pairs[i], Multi[i], Low[i], Up[i].

Restrictions: -25 <= Low[i] < Up[i] <= 25, 0 <= Pairs[i] <= 100000, 1 <= Multi[i] <= 20. From the input given, you may assume that there is always a solution.

Output

For each test case, output a single line with a single number, which is the largest

Sample Input

10
7 1 1 10
0 2 -10 10
2 2 -10 10
0 2 -10 10
0 1 1 10
0 2 -10 10
0 2 -10 10
0 1 1 10
0 2 -10 10
0 1 1 10

10
0 1 1 10
2 2 -10 10
2 2 -10 10
2 2 -10 10
0 1 1 10
2 2 -10 10
2 2 -10 10
0 1 1 10
2 2 -10 10
0 1 1 10

Sample Output

90
-4

Source

POJ Monthly--2006.01.22,Zeyuan Zhu

Solution:

这是一道经典的多重背包 DP(虽然我并不能看出来这是背包 TAT)。

首先,我们已知 Low[ i ] ≤ Table[ i ] ≤ Up[ i ]

那么可设 X[ i ] = Table[ i ] - Low[ i ],则 0 ≤ X[ i ] ≤ Up[ i ] - Low[ i ],此时

  • ∑ Multi[ i ] * Table[ i ] = 0  ⇔  ∑ Multi[ i ] * X[ i ] = - ∑ Multi[ i ] * Low[ i ]
  • ∑ Table[ i ] * Pairs[ i ]  ⇔  ∑ X[ i ] * Pairs[ i ] + ∑ Low[ i ] * Pairs[ i ]。

而 - ∑ Multi[ i ] * Low[ i ] 和 ∑ Low[ i ] * Pairs[ i ] 是可以预先求出的,所以题目转化为:

  • 有 M 种物品,第 i 种有 Up[ i ] - Low[ i ] 个,每个价值为 Pairs[ i ],体积为 Multi[ i ]
  • 选取部分或全部物品,装入一个容积为 - ∑ Multi[ i ] * Low[ i ] 的背包中且恰好装满
  • 求所能得到的最大价值与 ∑ Low[ i ] * Pairs[ i ] 的和。

多重背包可以使用二进制优化,即将 X 个相同物品分成 1, 2, 4, …, 2k-1, X-2k+1 这几组来处理。

看懂题意之后就 1A 了 ^v^

Code: O(TMC∑logRi) [1440K, 954MS]

其中 C 为最大容积(=1e5), Ri 为 Table[i] 上下界之差的最大值(=50)。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int M;
int v[205], w[205], cnt[205], cap;
ll dv, dp[100005];

int main(){
	while(scanf("%d", &M) != EOF){
		dv = cap = 0;
		for(register int i = 1; i <= M; i++){
			int Pairs, Multi, Low, Up;
			scanf("%d%d%d%d", &Pairs, &Multi, &Low, &Up);
			v[i] = Pairs, w[i] = Multi, cnt[i] = Up - Low;
			dv += Pairs * Low, cap -= Multi * Low;
		}
		memset(dp, 0xc0, sizeof(dp)), dp[0] = 0;
		for(register int i = 1; i <= M; i++){
			bool flag = 0;
			for(register int j = 1;; j <<= 1){
				if(cnt[i] < (j << 1)) j = cnt[i] - j + 1, flag = 1;
				// Binary Optimization: divide cnt[i] into 1, 2, 4, ..., 2^(k-1), cnt[i]-2^k+1
				int lb = j * w[i];
				for(register int k = cap; k >= lb; k--)
					dp[k] = max(dp[k], dp[k - lb] + j * v[i]);
				if(flag) break;
			}
		}
		printf("%lld\n", dp[cap] + dv);
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai