Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<queue>
- #include<algorithm>
- using namespace std;
- long long y=0;
- vector<long long> q;
- bool printknapSack(long long W, long long val[], long long n,long long y){
- long long i, w;
- long long x=0;
- long long K[n + 1][W + 1];
- for (i = 0; i <= n; i++) {
- for (w = 0; w <= W; w++) {
- if (i == 0 || w == 0){
- K[i][w] = 0;
- }
- else if (val[i - 1] <= w){
- K[i][w] = max(val[i - 1] +K[i - 1][w - val[i - 1]], K[i - 1][w]);
- }
- else{
- K[i][w] = K[i - 1][w];
- }
- }
- }
- if(K[n][W] == W){
- int res = K[n][W];
- w = W;
- for (i = n; i > 0 && res > 0; i--) {
- if (res == K[i - 1][w])
- continue;
- else {
- q.push_back(val[i-1]);
- res = res - val[i - 1];
- w = w - val[i - 1];
- }
- }
- return true;
- }
- else if(W == 0){
- return true;
- }
- else{
- return false;
- }
- }
- int main(){
- long long n;
- cin>>n;
- long long val[n];
- long long x;
- vector<long long>k;
- vector<long long>q1;
- long long temp;
- for(long long i=0;i<n;i++){
- cin>>val[i];
- y+=val[i];
- }
- int tr;
- tr = y/2;
- bool b=true;
- while(tr > 0){
- temp = y - (2 * tr);
- b = printknapSack(temp,val,n,y);
- if(b == true){
- if(temp != 0){
- while(!q.empty()){
- for(int i=0;i<n;i++){
- if(val[i] == q.back()){
- val[i] = 0;
- k.push_back(i);
- q1.push_back(q.back());
- q.pop_back();
- break;
- }
- }
- }
- }
- b = printknapSack(tr,val,n,y);
- if(temp != 0){
- while(!k.empty()){
- val[k.back()] = q1.back();
- k.pop_back();
- q1.pop_back();
- }
- }
- if(b == 1){
- break;
- }
- tr--;
- }
- else{
- tr--;
- }
- }
- if(tr == 0){
- cout<<y;
- }
- else{
- cout<<tr+temp;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment