my0-1knapsack.cpp

来自「给定n 个物品, 物品i重为wi 并且价值为 vi」· C++ 代码 · 共 46 行

#include<iostream>
using namespace std;
int main(){
    int n,c,w[101],p[101],v[101][2000],i,j,total=0,result[101];
	cout<<"****************  0-1 背包问题程序实例 **********************"<<endl;
	cout<<endl<<"请输入背包的容量C (C为0则程序结束)：";
	cin>>c;
	if (c==0) goto over;
	cout<<endl<<"请输入可供选择的物品的个数N (N为0则程序结束)：";
	cin>>n;
	while (n && c){
         cout<<endl<<"请输入"<<n<<"个物品的重量W和价值P:";
		 for(i=1;i<=n;i++){
			 cout<<endl<<"物品"<<i<<"---重量：";
			 cin>>w[i];
			 cout<<"        价值: ";
			 cin>>p[i];
		 }

		 for(i=1;i<=n;i++)
			 v[i][0]=0;
		 for(j=0 ;j<=c;j++)
			 v[0][j]=0;
		 for(i=1;i<=n;i++)
		    for(j=1;j<=c;j++){
				v[i][j]=v[i-1][j];
				if ((w[i]<=j) && (v[i][j]<v[i-1][j-w[i]]+p[i])) {                 
					   v[i][j]=v[i-1][j-w[i]]+p[i]; 
                       if(j==c)  result[++total]=i;
				}
			}
        cout<<"装满背包可获得的最大价值为："<<v[n][c]<<endl;
		cout<<"装入背包的物品为："<<endl<<"物品：";
		for(i=1;i<=total;i++)
			cout<<result[i]<<", ";
	
		total=0;
        cout<<endl<<endl<<"请输入背包的容量C (C为0则程序结束)：";
	    cin>>c;
        if (c==0) goto over;
        cout<<endl<<"请输入可供选择的物品的个数N (N不大于100，若为0则程序结束)：";
	    cin>>n;
	}
over:;	cout<<endl<<"***********   谢谢使用!    ***********"<<endl;
	return 1;
}