BALTIC2008 Elect

wjh15101051's space

卧薪尝胆，厚积薄发。

BALTIC2008 Elect

Date: Wed Sep 19 14:14:14 CST 2018

In Category: NoCategory

Description：

$n$ 件物品，要求总体积尽量大，但去掉任何一个物品后总体积都小于 $1/2$ 。

$1\le n \le 300,1\le \sum v_i\le 100000$

Solution：

先把所有物品从大到小排序做背包，然后把第一次突破 $1/2$ 的状态更新答案。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 310

#define MAXM 100000

int s[MAXN];

bool f[MAXN][MAXM];

bool cmp(int a,int b){return a > b;}

int main()

{

	scanf("%d",&n);

	int sum = 0;

	for(int i = 1;i <= n;++i)scanf("%d",&s[i]);

	sort(s + 1,s + 1 + n,cmp);

	for(int i = 1;i <= n;++i)sum += s[i];

	int mid = sum / 2; 

	f[0][0] = true;

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= mid;++j)

		{

			if(!f[i - 1][j])continue;

			f[i][j] = true;

			if(j + s[i] > mid)

			{

				ans = max(ans,j + s[i]);

			}

			else

			{

				f[i][j + s[i]] = true;

			}

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: DP-背包

wjh15101051