Skip to content

Instantly share code, notes, and snippets.

@jason810496

jason810496/01Knapsack

Created May 20, 2024 02:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jason810496/a8360b0dea7758a23a6645ad94808680 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jason810496/a8360b0dea7758a23a6645ad94808680 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
01Knapsack
38
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 8 | 14| 14| 14| 14| 14| 14| 14| 14| 14| 14| 14| 14|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 8 | 15| 15| 23| 23| 23| 29| 29| 29| 29| 29| 29| 29|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 8 | 15| 15| 23| 23| 23| 29| 29| 29| 29| 32| 32| 32|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 8 | 15| 15| 23| 23| 23| 29| 29| 29| 31| 32| 32| 32|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 13| 15| 15| 23| 23| 28| 29| 29| 34| 34| 34| 36| 37|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 8 | 8 | 13| 15| 15| 23| 23| 28| 29| 29| 34| 34| 34| 37| 38|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Raw
01Knapsack.cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector< pair<int,int> > vpii;
const int MAX_N = 1e5;
const int INF = 1e9;
const int MOD = 1e9+7;
/*
7
2 8
3 6
5 15
4 3
3 2
2 5
6 9
*/
void print_table(vvi &vec){
cout<<"+";
for(int i=0;i<vec[0].size();i++) cout<<"---+";
cout<<"\n";
for(int i=0;i<vec.size();i++){
cout<<"| ";
for(int j=0;j<vec[i].size();j++){
cout<<vec[i][j];
if( j!=vec[i].size()-1 && vec[i][j+1] > 9 && vec[i][j] <= 9 ){
cout<<" | ";
}
else if(vec[i][j] > 9){
cout<<"| ";
}
else{
cout<<" | ";
}
}
cout<<"\n";
cout<<"+";
for(int i=0;i<vec[0].size();i++) cout<<"---+";
cout<<"\n";
}
}
signed main(){
OAO
int n,wt=16;
cin>>n;
vi cost(n+1),value(n+1);
for(int i=1;i<=n;i++){
cin>>cost[i]>>value[i];
}
vvi dp(n+1,vi(wt+1));
for(int i=1;i<=n;i++){
for(int w=0;w<=wt;w++){
if( cost[i] > w ){
dp[i][w] = dp[i-1][w];
}
else{
dp[i][w] = max( dp[i-1][w] , dp[i-1][w-cost[i]]+value[i] );
}
}
}
cout<<dp[n][wt]<<"\n";
print_table(dp);
return 0;
}
Raw
01Knapsack.in
7
2 8
3 6
5 15
4 3
3 2
2 5
6 9
Raw
README.md 
g++ -std=c++11 01Knapsack.cpp
./a.out < 01Knapsack.in > 01Knapsack.out
diff 01Knapsack.out 01Knapsack
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment