0w1

Knapsack

Yuki 626 Randomized 01 Knapsack

Problem Description: 0/1 Knapsack problem. Test cases are generated at complete randomness.Constraints: 2 ≤ N ≤ 5000 v[i], w[i] is uniformly distributed in range [1, 1e12] 1 ≤ W ≤ 1e12 * NSolution: Branch and Bound. Referenced kimiyuki's b…

IOICJ 80 Buying Potions ( DP, Multiple Knapsack, Monotonous )

Problem Description: There are N shops that sell potions, and each of them only sells one kind of potion. The i'th shop sells potions for P[ i ] per glass, where each glass could heal B[ i ] units of health, but has only C[ i ] glasses in …

CFR 148 E. Porcelain ( DP, Knapsack )

Problem - E - Codeforces題意: 有 N 個雙向佇列,可以從左端或右端拿東西,東西用價值描述。求總共拿 M 個東西時,最大可能價值。資料規模: The first line of input data contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 10000). The next n line…

CFR 742 D. Arpa's weak amphitheater and Mehrdad's valuable Hoses ( DP, Knapsack, Union Find )

Problem - D - Codeforces題意: 給每個人的重量和權值。再給每對朋友的關係。x 和 y 屬於同個朋友圈,若存在一個序列 a[ 0 ], a[ 1 ], .. a[ i ],滿足所有相鄰的人都是朋友。對於每個朋友圈,可以選一個人,或選所有的人,或都不選,邀請到派對。但是派對…

JOI 11 本選 Night Market ( 区間DP )

Night Market | Aizu Online Judge ナップサック問題に変換するまでは簡単に見破れるが、問題はどう実装するかだ。愚直に解こうとするとO( n ^ 2 * t )になってしまうので、セグメント木を使いました。実は左からと右からとそれぞれ1回ずつナップサックをす…

ABC 32 D - ナップサック問題 ( 01Knapsack, 3 solutions )

D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder いい練習になった。 #include <bits/stdc++.h> using namespace std; const int MAXN = 200 + 5; typedef long long ll; typedef pair<ll, ll> pll; int n, c; int v[ MAXN ], w[ MAXN ]; void solve1(){ // n <= 30 </ll,></bits/stdc++.h>…

POJ 3260 The Fewest Coins ( Knapsack multiple & complete DP )

3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…