304 North Cardinal St.
Dorchester Center, MA 02124

# Knapsack Problem CodeChef Solution

## 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 << "]";}

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){
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){
}
else{
}
}
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 + " ");
}

}

StringTokenizer st=new StringTokenizer("");

String next() {
while(!st.hasMoreTokens())
try {
}
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

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 W=0;
for(int i = 0; i<N; i++)
{

int w = int.Parse(s[0]);

ulong cost  = UInt64.Parse(s[1]);
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()
return
}

func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
scanner.Scan()
return
}

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

func main() {
scanner := bufio.NewScanner(os.Stdin)
W := make([]int, n)
C := make([]int, n)
for i := 0; i < n; i++ {
}
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!