Two easy knapsack tasks

Revision en2, by lis05, 2021-09-17 13:19:20

Hello codeforces! Try to solve both of the problems from https://codeforces.net/contestInvitation/fcf424afaf5b7a5d01aebf1a908d6ef3589e4fb3. good luck

Solution:

This is a simple dp problem(very simple), but with a high constraints. Standard knapsack runtime is O(NW), but we can optimize it to run in O(NW/32) using bitset.

#include<bits/stdc++.h>
using namespace std;

const int N=2e5;
const int W=2e5;
bitset<W>b;
 
signed main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,w;
    scanf("%d %d",&n,&w);
    b[0]=1;
    while(n--){
        int a;
        scanf("%d",&a);
        b|=(b<<a);
    }
    if(b[w])printf("YES\n");
    else printf("NO\n");
}

How does it work? b[k] contains 0, if it's not possible to get sum k, and 1, if it's possible.

At start, we set b[0] to 1(because we can get sum 0). Next, for each item we left-shift out bitset by a[i]. new_b=b<<a[i] After this move, new bitset contains information about what can we get if we will take current item, but it ignores all previous moves(when we didn't take current item). To fix this, we need to connect two bitsets in one using bitwise or. new_new_b=new_b|b

To do this fast, we just write b|=(b<<a)

Why this works fast? in standard approach, we create array bool dp[n][w], and we do O(NW) operations with bool type, which has size of 4bytes on most systems.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English lis05 2021-09-17 13:49:04 17 Added solution (published)
en4 English lis05 2021-09-17 13:42:46 587 Tiny change: 'ary numbers(which con' -> 'ary number(which con'
en3 English lis05 2021-09-17 13:35:46 616
en2 English lis05 2021-09-17 13:19:20 1304 (saved to drafts)
en1 English lis05 2021-09-16 15:39:33 174 Initial revision (published)