Problem Link: https://lightoj.com/problem/funny-knapsack
Problem Clearance: First of all, it is not a straightforward knapsack or dynamic programming problem. So do not get afraid of it. Well, the problem said you will be given a target weight and some items of individual weight. You have to count the number of combinations that you can make by using the weight of the item that the sum of the individual weight will be less than the target value. For example, you will be given three items of 1, 2, 4 unit weight and your target weight is 10. So the combinations you will get that will be less than 10 are {0, 1, 2, 4, 1+2, 1+4, 2+4, 1+2+4} = 8. Now, you might be wondering why 0 is an answer. Taking nothing in your knapsack is lesser than the given weight. Hence, 0 is a valid answer.
Required Knowledge: Basic recursion, Sorting, Binary search, or Upper bound standard template library (STL).
Tutorial: I will try to share my thought process in this tutorial while solving this problem. I think that will be helpful for the reader. I would like to request you to take a notebook and try to illustrate the approach by hand with me.
Approach 1: So the first thought that came to my mind when I read this problem that it is a simple knapsack problem. Just run a recursion over the array, sum up the weight of the current item with the current cumulative weight and check the current cumulative weight is lesser than the target weight. If it is then increase the count. Return the count.
Then I calculated the complexity of my approach. The total number of the item could be as many as 30 and if I go through the above-mentioned process the total number of operations could be 230 = 1,073,741,824 which way more than the number of operations a modern CPU can do within 1 second. Then I also incorporate the complexity of test cases. So I have to drop the idea.
Approach 2: While thinking of the first approach you might get thought about why the number of items is that big. If this could be a little lower then you can solve the problem using the previously mentioned approach.
Well, what if we split the items list into two different parts. And do the recursion over those two already split arrays. So with the 30 items if we split into two parts of 15 elements. Let us assume there are two arrays ARR1 and ARR2. Now we will recurse over the first part of the given array. On every single recurse, we will either add the ith element with the propagated sum or we will skip the current one and move to the next one (the basic knapsack trick). When we reach the base case (at the end of the first part) we will store the current propagated sum into ARR1. We will do the similar for the rest of the elements of the given array and will store them into the ARR2. The pseudocode will be something like this -
// P = ith position in the array // S = size of the array // C = currently propagated sum // A = the array where the current combination sum will be stored. recurse_array(P, S, C, A) { if P is greater than S then return; if P is N insert C into A; // Store C into A insert (C + items[P]) into A; // Store sum of C and Pth item into A return; recurse_array(P+1, S, C+items[P], A); // Recurse with the Pth item recurse_array(P+1, S, C, A); // Recurse skipping the Pth item }
Before moving to the next part let's assume we have 4 items. The combination of free picking is 24 = 16, either we will take it or not, right? So what if we divide the four items into two groups of two items each. From the first group, the combination of free picking is 22 = 4. And from the second group, we will have 22 = 4 as well. Now if we consider for each free picking of the first group with each of the free pickings of the second group then we will have a similar result that we have got on 24. So, the total operation of 16 lower downed to 4+4 = 8. I hope you got my point about why I divided the array and recursed each one of them individually. We will use this concept to figure out the total combination. Moving to the next part.
Now consider the ARR1. Each stored element in the ARR1 is itself a combination. For each combination in ARR1, we will search for the rest of the combinations in ARR2. What we will do here is, we will subtract each of the ARR1 elements from the total given weight and search it into the ARR2. The returned index will denote the item with the higher most value for the ARR2 that we can consider for the combination that has a sum less than the given weight. That simply means we can take values less than or equal to the values of that index from the ARR2.
For example, we have a target weight of 10. In the ARR1 we have, {2, 3} and in the ARR2 we have {3, 7, 9}. Now if we consider ARR1[1] = 3 and subtract it from 10 we will have 10 - 3 = 7. We will search for items less than or equal to 7 from ARR2. We have the values {3, 7} less than or equal to 7. We will count these two values in.
To find out the total number of combinations, for each of the elements in ARR1, we will search the above-mentioned way in ARR2 and add the countings. As we are searching in an array where the order of the elements does not matter we will sort the ARR2 and run a binary search for speeding up the process.
Complexity Analysis: The first part consists of recursing N÷2 items of the given array which takes at most 2(N/2) operations. So the complexity is at most O(2N/2). As N is at most 30 and we have to do it twice (as we divided the array into two-part) it will take at most 215 = 32,768 x 2 = 65,536.
The second part contains sorting and binary search. The sorting costs O(Nlog2N) time complexity. For this part, the N will be at most 32,768 as we will be sorting ARR1 or ARR2. So sorting costs about 32768 x log2(32768) = 491,520 operations at most.
After sorting one (or both) of the arrays we will run a binary search on it to find our opted values. So for each item the binary search works on log2N = log2(32768) = 15. And for N items it will be Nlog2N = 32768 x log2(32768) = 491,520.
Overall the highest complexity is O(Nlog2N) which will easily pass the test cases.
STL Used: I have used sort() and upper_bound() STL to lower down the size of the code. I will write about the STL algorithm some other day.
That's all. Hope you understand the concept. You can see the implementation below if you want to.
Code:
=> Leave a comment if you have anything to share. Thank you.
/** ssavi. ICT-4 CoU **/
#include<bits/stdc++.h>
#define DIST(x1,x2, y1, y2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)))
#define DIST3D(x1,x2, y1, y2, z1, z2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)) + ((z1-z2)*(z1-z2)))
#define CLR(a) a.clear()
#define VCLR(a, n) for(int i=0; i<=n+3; i++) a[i].clear()
#define SIZE(a) a.size()
#define ERASE(a, b) memset(a, b, sizeof a)
#define pb push_back
#define LL long long
#define ULL unsigned long long
#define DBG cout<<"I Am Here"<<endl
#define DBGA(a) cout<<a<<endl
#define DBGI(b,a) cout<<b<<' '<<a<<endl
#define DBGL(i,s,e,b) or(int i=s; i<=e; i++) cout<<b<<endl
#define INF 1e9
#define INV 1e-6
#define SF(a) scanf("%I64d", &a)
#define PF(a) printf("%I64d\n", a)
#define sf(a) scanf("%d", &a)
#define pf(a) printf("%d\n", a)
#define pii pair<int,int>
#define PIS pair<double,string>
#define PII pair<LL,LL>
#define MAX 600005
#define CASE(i) printf("Case %d:", i);
#define PI acos(-1)
#define piis pair<int, string>
#define fast1 ios_base::sync_with_stdio(false);
#define fast2 cin.tie(0)
#define CHECK_BIT(var,pos) ((var & (1 << pos)) == (1 << pos))
#define LOOP(i, b, n) for(int i=b; i<=n; i++)
#define nl puts("")
#define popcount __builtin_popcount
#define valid(i,j,m,n) (i>=0 && i<n && j>=0 && j<m)
using namespace std;
/** -------------------------------------------------**/
/** Header And Definitions Ends Here. **/
/** -----------------------------------------------**/
int dx4[] = {0, 0, 1, -1}; int dy4[] = {1, -1, 0, 0};
int dx8[] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy8[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dxH[] = {2, 2, -2, -2, 1, 1, -1, -1}; int dyH[] = {1, -1, 1, -1, 2, -2, 2, -2};
const double GRS = (1 + sqrt(5))/2;
template<typename T> T power(T X, T P)
{
T ans = (T)1;
for(T i=1; i<=P; i++){
ans = ans * X;
}
return ans;
}
template<typename T> T ABS(T A, T B)
{
T ret = A - B;
if(ret<0) return -ret;
return ret;
}
LL MOD = 1000000007;
const LL BIGMAX = power(2,63) - 1;
template<typename T> T ADD(T X, T Y, T M)
{
if(X+Y<0)
return (X - M) + Y;
else if(X+Y>=M)
return X+Y-M;
else
return X+Y;
}
template<typename T> T prod(T a, T b, T c) // CUSTOM PRODUCT FUNCTION FOR BIG NUMBER MULTIPLICATION
{
T x = 0, y=a%c;
while(b > 0){
if(b%2 == 1){
x = ADD(x, y, c);
}
y = (y*2)%c;
b /= 2;
}
return x%c;
}
template<typename T> T bigmod(T a, T b){
T x = 1, y = a%MOD;
while(b > 0) {
if(b%2 == 1) {
x = prod(x,y, MOD);
}
y = prod(y,y, MOD);
b /= (LL)2;
}
return x;
}
template <typename T> T MODINVERSE(T a){
return bigmod(a, MOD-2);
}
template<typename T> T GCD(T x, T y) {
while ( y != 0 ) {
T z = x % y;
x = y;
y = z;
}
return x;
}
bool isvowel(char ch)
{
ch = toupper(ch);
if(ch=='A' || ch=='E' || ch=='I' || ch=='O' || ch=='U' || ch=='Y') return true;
return false;
}
/**----------------------------------------------------------------------------**/
/** Template Ends Here. Main Function And User Defined Functions Starts Here. **/
/**--------------------------------------------------------------------------**/
LL arr[33];
vector<LL>cost, another;
void getall(int pos, int n, LL cur, vector<LL>& vec)
{
if(pos>n) return;
if(pos==n){
vec.push_back(cur);
vec.push_back(cur+arr[pos]);
return;
}
getall(pos+1, n, cur+arr[pos], vec);
getall(pos+1, n, cur, vec);
}
int main()
{
int test;
scanf("%d", &test);
LOOP(caseno, 1, test){
cost.clear(); another.clear();
int n; LL W;
scanf("%d %lld", &n, &W);
for(int i=1; i<=n; i++) scanf("%lld", arr+i);
getall(1, n/2, 0, cost);
if(cost.size()==0) cost.push_back(0);
// for(int i=0; i<cost.size(); i++){
// cout<<cost[i]<<' ';
// }
// nl;
getall(n/2+1, n, 0, another);
if(another.size()==0) another.push_back(0);
sort(another.begin(), another.end());
// for(int i=0; i<another.size(); i++){
// cout<<another[i]<<' ';
// }
// nl;
int sz = cost.size();
LL tot = 0;
for(int i=0; i<sz; i++){
LL val = W - cost[i];
if(val>=0){
LL idx = upper_bound(another.begin(), another.end(), val) - another.begin();
tot+=idx;
}
}
CASE(caseno);
printf(" %lld\n", tot);
}
}=> Leave a comment if you have anything to share. Thank you.
No comments:
Post a Comment