backpack.cpp

这是经典的背包问题

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// 冯原

/*
	文件名称：	backpack
	项目名称：	背包问题
	创建者：	冯原
	创建时间：	9/24/2006
	最后修改时间：9/24/2004
	功能：		解决背包问题

	文件中的函数名称和简单功能描述：
		void search(int x, double* w, double t, int& sum, int n)
		递归函数,对于第x的位置,剩余需要满足总重量t时情况的操作

	文件中定义的全局变量和简单功能描述：
		无

	文件中用到的他处定义的全局变量及其出处：无
	与其他文件的依赖关系：无
*/

#include <iostream>
using namespace std;

//函数名称：search
//函数功能描述：递归函数,对于第x的位置,剩余需要满足总重量t时情况的操作
//函数调用之前的预备条件：递归到第x的位置,记录每件物品重量的数组w,剩余需要满足总重量t,物品总数n
//返回值（如果有的话）:void
//函数的输入参数：无
void search(int x, double* w, double t, int& sum, int n) {
	if (w[x] == t) sum ++;  //第x位置的物品重量等于剩余总重量时,sum加1,即可以放的方法加1
	
	if (x < n-1)  //x不是最后一个时,可以继续进行搜索,此时不取第x个位置的物品
		search(x+1, w, t, sum, n);
	
	if (x < n-1 && w[x] < t)  //x不是最后一个时,可以继续进行搜索,此时取第x个位置的物品
		search(x+1, w, t - w[x], sum, n);
		
}

void main() {
	int n, sum = 0;  //n为物品总数,sum为方法总数,初始为0
	double T;  //背包可容纳的总重量

	//以下为输入
	cout << "please input the number of things:" << endl;
	cin >> n;  //物品总数
	
	double* w = new double[n];  //建立数组,记录每件物品的重量

	cout << "please input the weight of each thing:" << endl;
	for (int i = 0; i < n; i ++)
		cin >> w[i];  //输入每件物品的重量,用数组w记录

	cout << "please input the overall weight that the backpack can put in:" << endl;
	cin >> T;  //输入背包可容纳的总重量

	search(0, w, T, sum, n);  //调用search函数,判断是否有解,有解的话能有多少种方法

	delete []w;

	//以下为输出
	cout << "Result:" << endl;

	if (sum > 0)  //有解时,输出方法数
		cout << "can do   " << sum << " methods" << endl;

	else if (sum == 0)  //无解
		cout<< "can't do" << endl;
}