Demo entry 6781875

背包问题

   

Submitted by jiachengyou on Jan 05, 2019 at 05:18
Language: C++. Code size: 2.2 kB.

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

//解决背包问题的程序 
void solve_packge_problem(const int max_volume,const int number,const vector<int> volume){
     stack<int> packed,temp;//packed用来保存已装的物品,temp是暂时保存packed时用的 
     int i,j;//用来控制循环 
     int pos;
	 int curr_volume;//当前装的物品总体积 
     pos=0;
     int flag=0; 
     curr_volume=0;
     while(pos<number){ 
        //每次重新循环都要再次初始化 
     	curr_volume=0;
     	while(!packed.empty())
     	packed.pop();
     	//每次循环指的是没有pos之前的元素,而且一定有pos元素 
     	for(i=pos;i<number;flag==0?i++:flag=0){
     		if(curr_volume<max_volume){
     			packed.push(volume[i]);
     			curr_volume+=volume[i];
     		}
     		if(curr_volume>max_volume){
     			curr_volume-=packed.top();
     			packed.pop();
     		}
     		if(curr_volume==max_volume){
     			//为了输出后不改变最后栈顶下面的元素,需要temp来保存之前的数据 
				while(!packed.empty()){
     			    cout<<packed.top()<<"\t";
     			    temp.push(packed.top());
     			    packed.pop();
     			}
     			while(!temp.empty()){
     				packed.push(temp.top());
     				temp.pop();
     			}
     			curr_volume-=packed.top();
     			packed.pop();
				cout<<endl; 
     		}
     		//关键的一部分,主要是每次遍历到最后一个元素后再进行回溯,以防出现漏掉的情况 
			if(packed.size()>1&&i==number-1){
				//找到该元素位置,下次循环从下一个位置开始 
				for(j=pos+1;j<number;j++){
					if(volume[j]==packed.top()){
						if(j==number-1){//解决一些存在的漏洞 
							curr_volume-=packed.top(); 
							packed.pop();
							j=pos;
						}
						else{
							curr_volume-=packed.top();
						    packed.pop();
				            i=j;
						    j=number-1;
						    if(i==number-1)
						    flag=1;
						} 
				    }
				}
			} 
     	}
     	pos++;
     }
} 

int main(){
	//1.输入相关参数 
	int max_volume;
	int number;
	vector<int> volume;
	cout<<"Please input the volume of the bag: ";
	cin>>max_volume;
	cout<<"Please input the number of the things: ";
	cin>>number;
	cout<<"The volume of the things are: ";
	int i,value;
	for(i=0;i<number;i++){
		cin>>value;
		volume.push_back(value);
	}
	//2.开始解决背包问题 
	cout<<"All the solutions :"<<endl;
	solve_packge_problem(max_volume,number,volume);
	return 0;
} 

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).