Weselna Intercyza - zadanie, algorytmika

Question

Witam,

Mam takie zadanie:

"Weselna Intercyza
Tuż po konferencji dla nauczycieli w ramach Akademii Programowania odbyło się wesele. Węzłem
małżeńskim połączyło się dwojga jego uczestników: Małgorzata i Jan. Gratulacjom i prezentom nie było
końca. Małżonkowie postanowili spisać intercyzę, aby sprawiedliwie podzielić otrzymane dary. I Ty
możesz im pomóc pisząc odpowiedni program. Zadanie jest następujące: Dysponując listą wartości
otrzymanych prezentów, trzeba podzielić je na dwie części tak, aby różnica ich wartości była jak
najmniejsza. Jeśli nie da podzielić po równo, Małgorzata otrzymuje więcej.

Wejście:
W pierwszym wierszu standardowego wejścia zapisano rozdzielając spacją, liczbę naturalną P (1 ≤ P ≤
150) – liczbę prezentów, a następnie ich wartości Wi (1 ≤ Wi ≤ 10 000, i = 1,2,3…P).

Wyjście:
W jednym wierszu standardowego wyjścia zapisz kwotę wartości prezentów Małgosi i Jasia, rozdzielając je spacją.

Przykłady
Wejście:
4
1 1 3 4
Wyjście:
5 4

Wejście:
5
10 5 10 5 5
Wyjście:
20 15

Wejście:
6
4 3 1 1 12 11
Wyjście:
16 16"

 

Sprobowalem zrobic to zadanie metoda zachlanna, ale przeszlo ono tylko na 50/100. Wydaje mi sie, ze aby zrobic to zadanie na maksymalna ilosc punktow nalezy uzyc do tego programowania dynamicznego, jednakze nie jestem w stanie wpasc na zaden sposob jak to zrobic, dlatego prosze o pomoc. 

Z gory dziekuje za wszystkie odpowiedzi.

Answer 1

To zadanie to zaimplementuj problem plecakowy. Możesz napisać O(T*W), gdzie W = T*max_waga(czyli tam 10^4) implementując problem plecakowy. Potem dodatkowe optymalizacje możesz zejść do O(T*W/64), czyli zakładając, że W = T*10^4, to średnio będziesz miał T^2*10^4 / 64, co pewnie wejdzie korzystajac z tego, że jest to plecak 0-1(czy mozna ułożyć daną wagę czy nie, a nie o jak najmniejszym koszcie), czyli możesz użyć bitseta. Wpisz sobie w internecie problem plecakowy i spróbuj to zrozumieć, jak nie zrozumiesz / masz jakieś pytania to pisz. Jak już zrozumiesz jak działa problem plecakowy to bitset, to prosta optymalizacja.

Comments

Tak to problem plecakowy, ale z...dwoma plecakami. Ciekawe zadanie.

---

@pasjonat_algorytmiki, Ale w złożoności algorytmów nie możemy napisać sobie o(t*w/64)...

---

No bitset to bitset, nie wiem jak ty chcesz to opisać. Każdy ma tam inne priorytety w nauce algorytmiki, ale ja osobiście zamiast pruć się o /64, wole się skupiać na rozumieniu, wymyślaniu ciekawych zadań i algorytmów. Powiesz komuś, że O(n*w/64) i większość osób zrozumie. Przecież te limity w tych zadaniach są tylko po to, żeby sobie oszacować potem, czy twój program zmieści się w limitach czasowych.

---

@pasjonat_algorytmiki, 

zrobilem to zadanie na 100/100. Oto moj kod:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

void solve(){
	int P; cin >> P;
	int tab[P];
	int sum = 0;
	for(int i=0; i<P; i++){ 
		cin >> tab[i];
		sum += tab[i];
	}
	
	int dp[2][sum/2+1];
	for(int i=0; i<2; i++)
		for(int j=0; j<sum/2+1; j++)
			dp[i][j] = 0;
		
	for(int i=0; i<P; i++){
		for(int j=1; j<sum/2+1; j++){
			if(j-tab[i] >= 0)
				dp[i%2][j] = max(dp[1-(i%2)][j], dp[1-(i%2)][j-tab[i]]+tab[i]);
			else
				dp[i%2][j] = max(dp[1-(i%2)][j], dp[i%2][j-1]);
		}
	}
	
	cout << sum - dp[1-(P%2)][sum/2] << " " << dp[1-(P%2)][sum/2] << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	solve();
		
	return 0;
}