FEBCON2 - Editorial


Author, Tester, Editorialist: John Zakkam



Unbounded Knapsack,dp


In a different world, the people there store the money in pots. They put their money in the pot at random whenever money comes to their hand. They don’t know exactly how much money they put into the pot every time. So that, whenever they need the money, they just break the pot. But they don’t know whether the amount of money in the pot will be sufficient for their need every time. That’s why you need to determine the minimum amount of money present in the pot given the amount of money that the pot can hold and the weight of each type of coin.You have to print exactly one line of output for each test case. The line should contain only " X" (without quotes)" where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “-1” (without quotes).


This is a DP solution. To get the solution for W=100, we’ll solve subproblems first. Let dp[W+1] be an array which will store the subproblems solutions. In the end, dp[W] will give us the minimum amount. Subproblems soultion will be the minimum of taking the coin Vk + solution for dp[ weight left after taking that coin ] or not taking that coin; where k ranges from 1 to N; meaning loop will run for all types of coins.


Setter's Solution
#include <bits/stdc++.h>
using namespace std;

int main(){
	int T,E,F,N,p[500],w[500],dp[10000];
	for(int tc = 1;tc<=T;++tc){
		scanf("%d %d %d",&E,&F,&N);
		for(int i = 0;i<N;++i) scanf("%d %d",&p[i],&w[i]);
		F -= E;
		dp[0] = 0;
		for(int i = 1;i<=F;++i){
			dp[i] = -1;
			for(int j = 0;j<N;++j)
				if(i>=w[j] && dp[i-w[j]]!=-1 && (dp[i]==-1 || p[j]+dp[i-w[j]]<=dp[i]))
					dp[i] = p[j]+dp[i-w[j]];
		if(dp[F]==-1) printf("-1\n");
		else printf("%d\n",dp[F]);
	return 0;