Knapsack Problem CodeChef Solution

Problem -Knapsack Problem CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>

Knapsack Problem CodeChef Solution in C++14

// Ref : _krugarr_

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
const int W = 1e7+10;

#define     EPS                  1e-9
#define     INF                  (int)1e9
#define     MOD                  1000000007

#define     ff                   first
#define     ss                   second
#define     tab                  "\t"
#define     endl                 "\n"
#define     gcd(x,y)             __gcd(x,y)
#define     lcm(x,y)             ( (x*y)/__gcd(x,y) )
#define     pb                   emplace_back
#define     gc                   getchar_unlocked
#define     eraseAt(a,index)     (a).erase( (a).begin() + index )
#define     all(a)               (a).begin(), (a).end()
#define     uniq(a)              (a).erase( unique(all(a)), (a).end() )
#define     repItr(i,a)          for(auto i: (a))
#define     rep(i,a,b)           for(ll i = a; i < b; i++)                 
#define     rrep(i,a,b)          for(ll i = a; i >= b; i--)                

#define     countLZ(x)           __builtin_clz(x)                          // returns the count of leading zeros in binary of a data upto first set(1) bit
#define     countTZ(x)           __builtin_ctz(x)                          // returns the count of trailing zeros in binary of a data from last set(1) bit
#define     checkbit(n,b)        ( (n >> b)&1 )                            
#define     parityCheck(x)       __builtin_parity(x)                       // returns 1(true) if odd number of set bits present in int, long data
#define     setbitCount(x)       __builtin_popcount(x)                     // returns the number of one’s(set bits) in binary of an int, long data
#define     PI                   3.1415926535897932384626433832795

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void    _print(ll t)       {cerr << t;}
void    _print(int t)      {cerr << t;}
void    _print(string t)   {cerr << t;}
void    _print(char t)     {cerr << t;}
void    _print(lld t)      {cerr << t;}
void    _print(double t)   {cerr << t;}
void    _print(ull t)      {cerr << t;}

template <class T, class V>  void _print(pair <T, V> p);
template <class T>           void _print(vector <T> v);
template <class T>           void _print(set <T> v);
template <class T, class V>  void _print(map <T, V> v);
template <class T>           void _print(multiset <T> v);
template <class T, class V>  void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T>           void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T>           void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T>           void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V>  void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

/*======================================================== End_Of_Header ========================================================*/

inline void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);        
    cout.tie(NULL);       
    #ifndef ONLINE_JUDGE  
        freopen("input_6.txt","r",stdin);
        freopen("output_6.txt","w",stdout);
    #endif
}

template <typename T> using V = vector<T>;
template <typename T> V<T> prefixSum(const V<T> &v) {
    int n = v.size(); V<T> ret(n + 1);
    rep(i, 0, n) ret[i + 1] = ret[i] + v[i]; return ret;
} 

inline int mod_32(int x, int divisor) {int m = x % divisor; return m + ((m >> 31) & divisor);}
inline ll mod_64(ll x, ll divisor) {ll m = x % divisor; return m + ((m >> 63) & divisor);}

// ll input[W]; ll Sum_Of[W];

bool isPowerOf2(ll n){ if(n&(n-1)) return false; else return true; }

/*======================================================= End_Of_Utilities =======================================================*/
void solve(){
    ll n,k,i,ans=0,b=0,c=1,j,x,w,c1,c2;
    cin>>n;
    vector<long> v2,v1;
    for(i=1;i<=n;i++){
        cin>>w>>x;
        if(w==1) v1.push_back(x);
        else v2.push_back(x);
        b+=w;
    }
    vector<vector<long>> dp(b+1,vector<long>(3));
    dp[0][0]=0; dp[0][1]=0; dp[0][2]=0;
    sort(v1.begin(),v1.end(),greater<long>());
    sort(v2.begin(),v2.end(),greater<long>());
    for(i=1;i<=b;i++){
        c1=0; c2=0;
        if(i>=1){
            c1=dp[i-1][0];
            j=dp[i-1][1];
            if(j<v1.size()) c1=c1+v1[j];
        }
        if(i>=2){
            c2=dp[i-2][0];
            j=dp[i-2][2];
            if(j<v2.size()) c2=c2+v2[j];
        }
        if(c1>=c2){
            dp[i][0]=c1; dp[i][1]=dp[i-1][1]+1;
            dp[i][2]=dp[i-1][2];
        }
        else{
            dp[i][0]=c2; dp[i][1]=dp[i-2][1];
            dp[i][2]=dp[i-2][2]+1;
        }
        cout<<dp[i][0]<<" ";
    }
    cout<<"\n";
}
int main(){
    io();
    ll tc = 1;
  while(tc-->0){
        solve();
    }
    return 0;
}

Knapsack Problem CodeChef Solution in PYTH 3


test = False
N = int(input())
ones = []
twos = []

for i in range(N):
    W, C = map(int, input().strip().split(' '))
    if test: print('W, C = ', W, C)
    if W == 1:
        ones.append(C)
    else:
        twos.append(C)

max_weight = len(ones) + 2 * len(twos)

if len(ones) >= 1:
    ones.append(0)
    ones.sort(reverse=True)

    even_twos = twos.copy()
    odd_twos = twos.copy()

    for i in range(1, len(ones)):
        if i % 2 == 1:
            even_twos.append(ones[i] + ones[i - 1])
        else:
            odd_twos.append(ones[i] + ones[i - 1])

    even_twos = sorted(even_twos)
    odd_twos = sorted(odd_twos)

    res = [0, ones[0]]

    for w in range(2, max_weight + 1):
        if w % 2 == 0:
            temp = even_twos.pop()
        else:
            temp = odd_twos.pop()
        res.append(res[w - 2] + temp)

else:
    res = [0, 0]
    twos = sorted(twos)
    for w in range(2, max_weight + 1):
        temp = 0
        if w % 2 == 0:
            temp = twos.pop()
        res.append(max(res[w - 2] + temp, res[w - 1]))
res.pop(0)
print(*res,sep = ' ')

Knapsack Problem CodeChef Solution in C

#include<stdio.h>
#include<stdlib.h>

long long int max(long long int a, long long int b)
{
    return (a>b)?a:b;
}

int compare_long_long_ints_desc(const void* a, const void* b)
{
    return *((const long long int*)(b)) - *((const long long int*)(a));
}

int main(void) {
	long long int N;
	scanf("%lld", &N);
	long long int* I[3];
	long long int Isize[3] = {};
	I[2] = malloc(sizeof(long long int) * N);
	I[1] = malloc(sizeof(long long int) * N);
	long long int M = 0;
	for(long long int i = 0; i < N; i++)
	{
	    long long int W;
	    long long int C;
	    scanf("%lld %lld", &(W), &(C));
	    M += W;
	    I[W][Isize[W]++] = C;
	}
	
	qsort(I[1], Isize[1], sizeof(long long int), compare_long_long_ints_desc);
	qsort(I[2], Isize[2], sizeof(long long int), compare_long_long_ints_desc);
	
	/*for(long long int i = 0; i < Isize[1]; i++)
	    printf("%lld ", I[1][i]);
	printf("\n");
	
	for(long long int i = 0; i < Isize[2]; i++)
	    printf("%lld ", I[2][i]);
	printf("\n");*/
	
	long long int* res = calloc(sizeof(long long int), (M+1));
	
	long long int* i[3];
	i[1] = calloc(sizeof(long long int), (M+1));
	i[2] = calloc(sizeof(long long int), (M+1));
	
	for(long long int m = 1; m <= M; m++)
	{
	    /*res[m] = 0;
	    i[1][m] = 0;
	    i[2][m] = 0;*/
	    res[m] = res[m-1];
	    i[1][m] = i[1][m-1];
	    i[2][m] = i[2][m-1];
	    if(m >= 1 && i[1][m-1] < Isize[1])
	    {
	        if(res[m] < res[m-1] + I[1][i[1][m-1]])
	        {
	            res[m] = res[m-1] + I[1][i[1][m-1]];
	            i[1][m] = i[1][m-1] + 1;
	            i[2][m] = i[2][m-1];
	        }
	    }
	    if(m >= 2 && i[2][m-2] < Isize[2])
	    {
	        if(res[m] < res[m-2] + I[2][i[2][m-2]])
	        {
	            res[m] = res[m-2] + I[2][i[2][m-2]];
	            i[1][m] = i[1][m-2];
	            i[2][m] = i[2][m-2] + 1;
	        }
	    }
	}
	    
	free(I[2]);
	free(I[1]);
	free(i[2]);
	free(i[1]);
	
	for(long long int i = 1; i <= M; i++)
	    printf("%lld ", res[i]);
	printf("\n");
	
	free(res);
	return 0;
}

Knapsack Problem CodeChef Solution in JAVA

import java.io.*;
import java.util.*;

class c{
	public static void main(String [] arg){
		FastReader f = new FastReader();
		ArrayList<Integer> w1 = new ArrayList<>();
		ArrayList<Integer> w2 = new ArrayList<>();
		int n = f.nextInt();
		for(int i=0;i<n;i++){
			if (f.nextInt()==1){
				w1.add(f.nextInt());
			}
			else{
				w2.add(f.nextInt());
			}
		}
		Collections.sort(w1,Collections.reverseOrder());
		Collections.sort(w2,Collections.reverseOrder());
		
	        int i=0,j=0;
	        long ans=0;
	        int cw=0;
	        long w = w1.size()+2*w2.size();
	
	        for(int k=1;k<=w;k++){
	            long ans1=ans, ans2=ans;
	
	            if(k-cw==1) {
	                if (i < w1.size()) ans1 += w1.get(i);
	                if (i >= 1 && j < w2.size()) ans2 = ans2 - w1.get(i - 1) + w2.get(j);
	
	                if (ans1>ans && ans1>=ans2) {
	                    i++;
	                    ans = ans1;
	                    cw++;
	                } else if (ans2 > ans) {
	                    i--;
	                    j++;
	                    ans = ans2;
	                    cw++;
	                }
	            }
	
	            else if(j<w2.size()){ans += w2.get(j); j++; cw+=2;}
	
	            System.out.print(ans + " ");
	        }
	        
	}

	static class FastReader{
		
		StringTokenizer st=new StringTokenizer("");
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String next() {
			while(!st.hasMoreTokens()) 
				try {
					st=new StringTokenizer(br.readLine());
				}
			   catch(IOException e){
				   e.printStackTrace();
			   }
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		}
}

Knapsack Problem CodeChef Solution in PYPY 3

# cook your dish here
import sys
input=sys.stdin.buffer.readline


n=int(input())
w1=[]
w2=[]
# c=[0]
for i in range(n):
    wi,ci=[int(x) for x in input().split()]
    if wi == 2 :
        w2.append(ci)
    else:
        w1.append(ci)

w1.sort()
w2.sort()


w1o=w1.copy()
w2o=w2.copy()

m=len(w2)*2 + len(w1)

curr=0
ans=[0 for i in range(m+1)]
for w in range(2,m+1,2):
    cost1=0
    cost2=0
    flag=0
    if len(w2) >=1 :
        cost1 = w2[-1]
    
    if len(w1) >=2 :
        cost2=w1[-1]+w1[-2]
        flag=2
    elif len(w1) >=1 :
        cost2 = w1[-1]
        flag=1
    
    if cost1 > cost2:
        curr+=cost1
        ans[w] = curr
        w2.pop()
    else:
        curr+=cost2
        ans[w] = curr
        while flag > 0:
            w1.pop()
            flag-=1

# print(ans)


curr=0
if len(w1o) >=1:
    curr=w1o.pop()
    ans[1]=curr

ans[1]=curr
w1=w1o
w2=w2o
for w in range(3,m+1,2):
    cost1=0
    cost2=0
    flag=0
    if len(w2) >=1 :
        cost1 = w2[-1]
    
    if len(w1) >=2 :
        cost2=w1[-1]+w1[-2]
        flag=2
    elif len(w1) >=1 :
        cost2 = w1[-1]
        flag=1
    
    if cost1 > cost2:
        curr+=cost1
        ans[w] = curr
        w2.pop()
    else:
        curr+=cost2
        ans[w] = curr
        while flag > 0:
            w1.pop()
            flag-=1

print(" ".join([str(c) for c in ans[1:]]))

Knapsack Problem CodeChef Solution in PYTH

n = int(raw_input())
f = [[], []] 
total = 0 
for _ in xrange(n):
    w, c = map(int, raw_input().split())
    f[w%2] += c, 
    total += w
ans = [0] * (total + 1)
f = [sorted(i, reverse = 1) for i  in f]
pairs = [[] for _ in xrange(total + 1)]
pairs[0] = (0, 0)
def update(i, s, p):
    if s > ans[i]:
        ans[i] = s 
        pairs[i] = p
    
for e in xrange(1,total+1):
    ans[e] = ans[e-1] 
    i,j = pairs[e] = pairs[e-1]
    update(e, ans[e-1] + sum(f[1][j:j+1]) , (i, j + 1))      #pick the next 1 one
    if e >= 2:
        i,j = pairs[e-2]
        update(e, ans[e-2] + sum(f[1][j:j+2]) , (i, j + 2))  #pick the next 2 ones
        update(e, ans[e-2] + sum(f[0][i:i+1])  , (i+1, j ))  #pich the next two
    print ans[e],
    
    
#weight chỉ có 1 và 2, sort weight 1 và 2 theo giá trị giảm dần của values 
#think of w is a collections of 1s and 2s, suppose w = 1 * i + 2 * j then we will pick the first i 1s and the first js 2th 
#=>linear algorithm, at each index store the pair (i,j) which make w has maximum value
#3 case:
#from w-1, pick the next one
#from w - 2, pich the next 2 ones
#from w-2, pick the next two
#just update and select the maximum value

Knapsack Problem CodeChef Solution in C#

using System;
using System.Collections.Generic;

public class Test
{
    public static void Main()
    {
        List<ulong> one = new List<ulong>();
        List<ulong> two = new List<ulong>();
        ulong[] ans = new ulong[200001];
        int N = int.Parse(System.Console.ReadLine());
        int W=0;
        for(int i = 0; i<N; i++)
        {
            string[] s = System.Console.ReadLine().Split(' ');
            
            int w = int.Parse(s[0]);
            
            ulong cost  = UInt64.Parse(s[1]);
            if(w==1) one.Add(cost);
            else two.Add(cost);
            W+=w;
            
        }
        one.Sort();
        two.Sort();
        List<ulong> oneD = new List<ulong>(one);
        List<ulong> twoD = new List<ulong>(two);
        ulong current = 0;
        for(int i=2;i<=W;i+=2)
        {
            ulong cost1=0,cost2=0;
            int flag = 0;
            if(two.Count>=1) cost2 = two[two.Count-1];
            if(one.Count>=2) { cost1 = one[one.Count-1];cost1+= one[one.Count-2];
                                flag = 2;}
                                else if(one.Count>=1) { cost1 = one[one.Count-1];flag =1;}
            if(cost2>cost1) 
                { 
                    current+=cost2;two.RemoveAt(two.Count-1);
                }
            else { current+=cost1;
                    if(flag==2) {
                    one.RemoveAt(one.Count-1);
                    one.RemoveAt(one.Count-1);}
                    else {
                        one.RemoveAt(one.Count-1);}
                    }
            ans[i]+=current;     
            
        }
        one = oneD;
        two = twoD;
        //Console.Error.WriteLine(one.Count + " " + two.Count);
        current = 0;
        if(one.Count >=1) 
        {
            current+=one[one.Count-1];
            one.RemoveAt(one.Count-1);
            ans[1]=current;
        }
        for(int i=3;i<=W;i+=2)
        {
            ulong cost1=0,cost2=0;
            int flag = 0;
            if(two.Count>=1) cost2 = two[two.Count-1];
            if(one.Count>=2) { cost1 = one[one.Count-1];cost1+= one[one.Count-2];
                                flag = 2;}
                                else if(one.Count>=1) { cost1 = one[one.Count-1];flag =1;}
            //Console.Error.WriteLine(two.Count + " " + flag);
            if(cost2>cost1) 
                { 
                    current+=cost2;two.RemoveAt(two.Count-1);
                }
            else { current+=cost1;
                    
                    if(flag==2) {
                    one.RemoveAt(one.Count-1);
                    one.RemoveAt(one.Count-1);
                
                    }
                    else {
                        one.RemoveAt(one.Count-1);}
                    }
            ans[i]+=current;     
            
        }
        for(int i = 1;i<=W ; i++)
        {
            if(i>1) System.Console.Write(" ");
            System.Console.Write(ans[i]);
        }
        
    }
}

Knapsack Problem CodeChef Solution in GO

package main

import (
	"sort"
	"bufio"
	"os"
	"fmt"
)

func readInt(bytes []byte, from int, val *int) int {
	i := from
	tmp := 0
	for i < len(bytes) && bytes[i] != ' ' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp
	return i
}

func readNum(scanner *bufio.Scanner) (a int) {
	scanner.Scan()
	readInt(scanner.Bytes(), 0, &a)
	return
}

func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
	scanner.Scan()
	x := readInt(scanner.Bytes(), 0, &a)
	readInt(scanner.Bytes(), x+1, &b)
	return
}

func readNNums(scanner *bufio.Scanner, n int) []int {
	res := make([]int, n)
	x := -1
	scanner.Scan()
	for i := 0; i < n; i++ {
		x = readInt(scanner.Bytes(), x+1, &res[i])
	}
	return res
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := readNum(scanner)
	W := make([]int, n)
	C := make([]int, n)
	for i := 0; i < n; i++ {
		W[i], C[i] = readTwoNums(scanner)
	}
	res := solve(n, W, C)
	fmt.Printf("%d", res[0])
	for i := 1; i < len(res); i++ {
		fmt.Printf(" %d", res[i])
	}
	fmt.Println()
}

func solve(n int, W []int, C []int) []int64 {
	vc := make([]int, n)
	i, j := 0, n-1
	for k := 0; k < n; k++ {
		if W[k] == 1 {
			vc[i] = C[k]
			i++
		} else {
			vc[j] = C[k]
			j--
		}
	}

	sort.Ints(vc[:i])
	sort.Ints(vc[j+1:])

	var S int
	for a := 0; a < n; a++ {
		S += W[a]
	}
	res := make([]int64, S+1)

	var cur int64
	for w, u, v := 2, n-1, i-1; w <= S; w += 2 {
		if u == j && v < 0 {
			break
		}
		var x, y int64
		if u > j {
			x = int64(vc[u])
		}
		if v > 0 {
			y = int64(vc[v] + vc[v-1])
		} else if v == 0 {
			y = int64(vc[v])
		}
		if x > y {
			cur += x
			u--
		} else {
			cur += y
			v--
			v--
		}
		res[w] = cur
	}
	cur = 0
	if i > 0 {
		cur = int64(vc[i-1])
		i--
	}
	res[1] = cur
	for w, u, v := 3, n-1, i-1; w <= S; w += 2 {
		if u == j && v < 0 {
			break
		}
		var x, y int64
		if u > j {
			x = int64(vc[u])
		}
		if v > 0 {
			y = int64(vc[v] + vc[v-1])
		} else if v == 0 {
			y = int64(vc[v])
		}
		if x > y {
			cur += x
			u--
		} else {
			cur += y
			v--
			v--
		}
		res[w] = cur
	}

	return res[1:]
}
Knapsack Problem CodeChef Solution Review:

In our experience, we suggest you solve this Knapsack Problem CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Knapsack Problem CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Knapsack Problem CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *