Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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 valueKnapsack 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.
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!
