atcoder knapsack 2 - Codeforces

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
34:55:08
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 37:05:06

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя zeyad_alaa

atcoder knapsack 2

Автор zeyad_alaa, история, 5 лет назад, По-английски

Hello so this is my first blog, I solved knapsack 1 but cant find any solution to solve V2 : https://atcoder.jp/contests/dp/tasks/dp_e

can any one help me ?

#dynamic programing, atcoder

zeyad_alaa
5 лет назад
29

Комментарии (21)

Показать архивные | Написать комментарий?

rubai_99

5 лет назад, # |

← Rev. 2 →

first you have to find value per weight,then you sort them in descending order. then take one by one

→ Ответить

MidoriFuse

5 лет назад, # |

+10

This is a variant of the classic knapsack.

Notice that value is small (at most $$$10^5$$$ for all $$$100$$$ items), so instead of "what is the most value we can carry with weight $$$W$$$", you find "what is the least weight you need to carry to get a value of $$$V$$$".

→ Ответить

moli2398

4 года назад, # ^ |

Can it be done using top-down approach?

→ Ответить

MidoriFuse

4 года назад, # ^ |

I don't see why not :)

The parameters are (the item we are considering, the value we have taken so far) for $$$100*10^5$$$ states. The choices for each state are still "take the item" and "ignore the item", just like in usual knapsack.

Maybe memory limit might be an issue, but I've never had problems with $$$10^7$$$ integer states.

→ Ответить

moli2398

4 года назад, # ^ |

Can't seem to figure it out! If I include the element, I add its weight. And when I don't include the element, I don't add its weight. I have to take the minimum of both the choices. What will be the base case? When I reach the end of the array, I simply return 0.

public static int solve2(int n, int w, int[][] arr, int maxV) {
		dp=new int[n+1][maxV+1];
		for(int[] row:dp) {
			Arrays.fill(row, Integer.MAX_VALUE);
			
		}
		
		solveMemo(arr,0,0);
		for(int i=maxV;i>-1;--i) {
			if(dp[n-1][maxV]<=w) {
				return i;
			}
		}
		
		return 0;

	}
	
	static int[][] dp;
	
	public static int solveMemo(int[][] arr, int maxV,int idx) {
		if(idx==arr.length) {
			return 0;
		}
		
		if(dp[idx][maxV]!=Integer.MAX_VALUE) {
			return dp[idx][maxV];
		}
		
		int include = arr[idx][0] + solveMemo(arr,maxV+arr[idx][1],idx+1);
		int not = solveMemo(arr,maxV,idx+1);
		
		
		return dp[idx][maxV]=Math.min(include, not);
	}

But it doesn't seem to work! I also seem to understand while writing that it won't work. Where is it wrong and how do I make it work?

→ Ответить

MidoriFuse

4 года назад, # ^ |

Recurrence looks ok to me :) But there are some issues in solve2 I think.

int only holds up to $$$2^{31} - 1$$$, so it should overflow.

Also in this if else

if(dp[n-1][maxV]<=w) {
	return i;
}

Shouldn't it be more like this?

if(dp[n-1][i]<=w) {
	return i;
}

→ Ответить

moli2398

4 года назад, # ^ |

← Rev. 2 →

Fixed the solve2 method and overflow. Still doesn't give the correct answer. There's some issue in the recursion. Take case:

while calling recursion, at first, it goes on to include all elements, that is the first call, and then hits the base case from where it returns zero. Then the second call i.e. the not include case is called for the last element, from where it gets 0 from the base case. Now dp[n-1][maxV-valueOfLastElement]=0 because of the not include case. Isn't this wrong because it says to get value of [maxV-valueOfLastElement], we need only 0 weight. It didn't add up the weights of previously selected elements.

→ Ответить

MidoriFuse

4 года назад, # ^ |

← Rev. 2 →

Yeah looks like we missed that part :)

I guess we're both messing up the definitions a bit here. Usually we define dp(i, V) as "first i items, we are allowed to take V more values". So the answer should be dp(N, initialV), and the recurrence actually goes backwards from $$$N$$$ to $$$0$$$ (and likewise, from $$$maxV$$$ to $$$0$$$).

So you can implement the same recurrence but backwards (i.e. "if I include the element, I decrease $$$maxV$$$"), and do

for(int i = maxV;i>-1;--i) {
	if (solve(arr, N, i) <= w) {
		return i;
	}
}

→ Ответить

dark__forest

5 лет назад, # |

You may consider iterating over sum of values rather than weights as per the constraints..So making the definition of dp[i] as minimum weight that can be taken with exactly i value..you can iterate on items and value(since constraints on value is low) My submission..https://atcoder.jp/contests/dp/submissions/10848260 ..Also you can refer to Youtube video by Errichto for the same

→ Ответить

itsfourtobarcelonaaaa

11 месяцев назад, # ^ |

can you please tell why we say "min weight to achieve exactly this value V" and not min weight to achieve atleast V, or maybe even higher, i mean in 01 problem we dont keep W as an absolute goal, we take any weight less than W, so why are we asking for an exact goal for V? it might be a dumb ques but im new to dp so :(

→ Ответить

zeyad_alaa

5 лет назад, # |

MidoriFuse dark__forest thanks guys, that helped me

→ Ответить

LanceTheDragonTrainer

5 лет назад, # |

An alternative is Branch and Bound algorithm. Don't simply look at its theoretical time complexity. It works wonders in practice.

→ Ответить

SPyofgame

5 лет назад, # |

← Rev. 2 →

You can try Branch and Bound to run faster

Spoiler

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vmb;   /// Matrix boolean using vector
typedef vector<vll> vmll; /// Matrix long long using vector
 
const int INF = 1e9;
 
/// Top-down knapsack using Branch and bound approach
/// dp:     calculate subproblem
/// isDone:   if subproblem is calculated before
/// weight: weight of element
/// value:  value of element
/// n: length of array
/// i: index
/// j: weight
int tdkp01(vmll &dp, vmb &isDone, vi &weight, vi &value, int n, int i, int j)
{
    if (j <= 0)     /// Cant take more elements
        return 0;
 
    if (i == n)     /// End of array
        return INF;
 
    if (isDone[i][j]) /// If solved before
        return dp[i][j];
 
    isDone[i][j] = true; /// Solving Recursively
    return dp[i][j] = min(tdkp01(dp, isDone, weight, value, n, i + 1, j),
                          tdkp01(dp, isDone, weight, value, n, i + 1, j - value[i]) + weight[i]);
}

/// Finding max sum where total weight <= limit
int kp01(vmll &dp, vmb &isDone, vi &weight, vi &value, int n, int k, int vsum)
{
    vsum++;
    while (vsum--) /// Finding from limit -> 0 for faster ending
        if (tdkp01(dp, isDone, weight, value, n, 0, vsum) <= k)
            return vsum;
 
    return 0;
}
 
int main()
{
    int n, k;
    cin >> n >> k;
 
    vi weight(n), value(n);
    int vsum = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> weight[i] >> value[i];
        vsum += value[i];
    }
 
    vmll dp(n + 1);
    vmb isDone(n + 1);
    for (int i = 0; i <= n; ++i)
    {
        dp[i].assign(vsum, 0);
        isDone[i].assign(vsum, 0);
    }
 
    cout << kp01(dp, isDone, weight, value, n, k, vsum);
    return 0;
}

→ Ответить

LanceTheDragonTrainer

5 лет назад, # ^ |

← Rev. 3 →

It should be noted that the Branch and Bound algorithm doesn't always run fast. It's runtime depends on the accuracy and speed of the cost-estimation function. The better the cost-estimation function, the faster your answer will attain the optimum value. In this case, the cost-estimation function is both good and fast, so Branch and Bound works.

p.s. I don't think you understand how Branch and Bound works. It seems to me that your code uses DP instead of Branch and Bound.

→ Ответить

SPyofgame

5 лет назад, # ^ |

Yes. Thank you for reminding me. Since I always adding Branch and Bound for faster in some specific problems, I forgot to notice that not at every time it work faster than normal approach

→ Ответить

pz1971

5 лет назад, # |

This helped me.

→ Ответить

apnakaamkar

5 лет назад, # |

← Rev. 2 →

How to solve Knapsack-2 in single-d array? Anyone? This is my code and i am really stuck.

#include <iostream>
#include<vector>
using namespace std;

int main() {
   int  n,w,gmax=0;
   cin>>n>>w;
   vector<int> weights(n,0),values(n,0);

   for(int i=0;i<n;i++)
    cin>>weights[i]>>values[i];

   vector<long long int> dp(100001);

   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<100001;j++)
       {

           if(j==0)
           {
               dp[j]=0;
               continue;
           }

           if(i==0)
           {
               dp[j]=w+1;
               continue;
           }

           if(values[i-1]<=j)
           {
               dp[j]=min(weights[i-1]+dp[j-values[i-1]],dp[j]);
           }
       }
   }
    
    for(int j=0;j<100001;j++)
       {
           if(dp[j]<=w)
            gmax=max(gmax,j);
       }

   cout<<gmax;

   return 0;
}

→ Ответить

Everule

5 лет назад, # ^ |

← Rev. 2 →

Please put codes in spoilers. Your code is incorrect because You do not know if $$$dp[j-values[i-1]]$$$ has already used your current object and you may use it again. To fix that, you may iterate $$$j$$$ in reverse, so you know for a fact $$$dp[j-value[i-1]]$$$ is untouched.

→ Ответить

apoorva222g

5 лет назад, # |

Refer to this solution in which I have explained Knapsnack 0-1 with all possible implementation 1. Recursive Memoisation 2. Tabulation: space O(n^2) 3. Tabulation: space O(n) 4. The special case when max capacity is large, done using tabulation.

→ Ответить

apnakaamkar

5 лет назад, # ^ |

Thanks

→ Ответить

Letscode_sundar

16 месяцев назад, # |

The important observation here is to notice that, the total sum of the values will be 1e5 at max.

Now the states for dp are index and value to be constructed. dp[i][val] represents the minimum weight needed to construct val with i indices.

Click to view solution

void solve()
{
       int n=0,m=0,k=0,x=0,count=0,sum=0,ans=0;
       int w;
       cin>>n>>w;
       
       vi wt(n), v(n);
       FOR(i,0,n){
       	cin>>wt[i]>>v[i];
       	sum += v[i];
       }
       
       int MAX = sum;
       vector<int> prev(MAX+1), cur(MAX+1);
              
       for(int j=1;j<=MAX;j++){
       	prev[j] = INT_MAX;
       }
       prev[0] = 0;
       
       for(int i=1;i<=n;i++){
       	for(int j=1;j<=MAX;j++){
       		if(v[i-1]>j){
       			cur[j] = prev[j];
       		}		
       		else{
       			cur[j] = prev[j];
       			
       			if(prev[j-v[i-1]] <= w-wt[i-1]){
       				cur[j] = min(cur[j],wt[i-1]+prev[j-v[i-1]]);
       			}
       		}
       	}
       	prev = cur;
       }
       for(int i=MAX;i>=0;i--){
       	if(cur[i]<=w){
       		cout<<i;
       		break;
       	}
       }  
       
}

Link to my Submission

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.12.2024 06:39:54 (l2).

Десктопная версия, переключиться на мобильную.

При поддержке