Algorithm
Problem link- https://www.spoj.com/problems/WACHOVIA/
WACHOVIA - Wachovia Bank
Danilo Gheyi is a renowned bank robber. He is known worldwide for accomplishing the most profitable bank robbery, in Fortaleza, Ceará. Danilo and his friends dug a tunnel to get into the main chest. There were some bags, with different amounts of money or jewelry and weight. They had to leave about 50% of the total value, since the truck couldn't carry all the bags.
Danilo wasn't caught, and to show that he can do itall again, he is planning a robbery to one of the safer banks in USA -the Wachovia Bank. He wants your help to maximize the amount stolen, avoiding a huge loss as it happened in Fortaleza.
Write a program that, given the maximum weight the truck is ableto carry and the information about each bag in the bank, determine the maximum value that Danilo can steal.
Input
The input consists of several instances. There is an integer N (1 ≤ N ≤ 200) in the first line; it stands for the number of instances. The first line of each instance contains two integers, K and M (8 ≤ K ≤ 1000 and 1 ≤ M ≤ 50) representing, respectively, the maximum weight the truck can handle and the amount of bags in the bank. The next M lines describe each bag with two integers A and B (8 ≤ A ≤ 200 and 1 ≤ B ≤ 25): the weight and the value of the bag, respectively.
Output
For each instance output a sentence “Hey stupid robber, you can get P.”, and P represents the maximum value Danilo can steal.
Example
Input: 3 34 5 178 12 30 1 13 7 34 8 87 6 900 1 900 25 100 10 27 16 131 9 132 17 6 5 6 23 56 21 100 25 1 25 25 25 100 2 Output: Hey stupid robber, you can get 8. Hey stupid robber, you can get 25. Hey stupid robber, you can get 99.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b) si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
int wt[55];
int value[55];
int dp[1005][55];
int f(int W, int n){
if(n == 0)
return 0;
if(dp[W][n] != -1)
return dp[W][n];
if(wt[n-1] > W){
dp[W][n] = f(W, n-1);
return dp[W][n];
}
dp[W][n] = max(value[n-1] + f(W-wt[n-1], n-1), f(W, n-1));
return dp[W][n];
}
int main(){
io;
int t;
cin >> t;
while(t--){
memset(dp, -1, sizeof(dp));
int W, n;
cin >> W >> n;
for(int i = 0;i < n; i++){
cin >> wt[i] >> value[i];
}
int ans = f(W, n);
cout << "Hey stupid robber, you can get ";
cout << ans << "." <<endl;
}
return 0;
}Input
34 5
178 12
30 1
13 7
34 8
87 6
900 1
900 25
100 10
27 16
131 9
132 17
6 5
6 23
56 21
100 25
1 25
25 25
100 2
Output
Hey stupid robber, you can get 25.
Hey stupid robber, you can get 99.
#2 Code Example with Java Programming
Code -
Java Programming
import java.util.*;
import java.math.*;
import java.io.*;
class Wachovia
{
public static void main(String args []) throws IOException
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(System.out, true);
String str[]=in.readLine().split(" ");
int W=Integer.parseInt(str[0]);
int n=Integer.parseInt(str[1]);
int val=0,wt=0;
int max=W;int ans[][]=new int [3][max+1];
int mar[][]=new int[2] [max+1];
int last=0,use=0;
//int small=Integer.MAX_VALUE;
for(int j=1; j<=n; j++)
{
String si[]=in.readLine().split(" ");
val=Integer.parseInt(si[0]);wt=Integer.parseInt(si[1]);
int jmt=j%3,jit=(j-1)%3;last=jmt;
//small=small<wt?small:wt;
for(int k=wt; k<=max; k++)
{
/*if(wt>k)
{ans[jmt][k]=ans[jit][k];}
else*/
//ans[jmt][k]=Math.max((val+ans[jit][k-wt]),ans[jit][k]);
if(j%2!=0)
{//pw.print(mar[0][k]+" "+mar[0][k-wt]+"GF");
ans[jmt][k]=Math.max((val+mar[0][k-wt]),mar[0][k]);
mar[1][k]=mar[1][k]>ans[jmt][k]?mar[1][k]:ans[jmt][k];
}
else
{
//pw.print(mar[1][k]+" "+mar[1][k-wt]+"GF");
ans[jmt][k]=Math.max((val+mar[1][k-wt]),mar[1][k]);
mar[0][k]=mar[0][k]>ans[jmt][k]?mar[0][k]:ans[jmt][k];
pw.print(mar[0][k]+" ");
}
}
pw.println();
}
System.out.println( ans[last][max]);
}
}Input
34 5
178 12
30 1
13 7
34 8
87 6
900 1
900 25
100 10
27 16
131 9
132 17
6 5
6 23
56 21
100 25
1 25
25 25
100 2
Output
Hey stupid robber, you can get 25.
Hey stupid robber, you can get 99.
Demonstration
SPOJ Solution-Wachovia Bank-Solution in C, C++, Java, Python