背包问题1（递归算法）.cpp

来自「这是经典的背包问题」· C++ 代码 · 共 66 行

/*
我真诚地保证
我自己独立地完成了整个程序从分析、设计到编码的所有工作。

如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
详细地列举我所遇到的问题，以及别人给我的提示。

我的程序里中凡是引用到其他程序或文档之处，

我都已经在程序的注释里很清楚地注明了引用的出处。

我从未抄袭过别人的程序，也没有盗用别人的程序，

不管是修改式的抄袭还是原封不动的抄袭。

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

学号：00548250 
姓名：卞超轶

*/

#include <iostream.h>
#include <assert.h>            

void put(int T, int *weight, int num, int start, bool &f)   //用来判断是否能恰好装满
{
	if (T == 0)
		f = true;             //恰好装满
	if (f)
		return;               //递归出口
	for (int i = start; i < num; i++)             //从上次所取商品后一个商品开始尝试，避免重复尝试
		if (T >= weight[i])                       //剩余载重不小于商品重量
			put(T - weight[i], weight, num, i + 1, f);     //递归   
}

void main()
{
	int n, t;
	cout << "请输入商品的数量： ";
	cin >> n;
	assert(n > 0);                //商品数量大于零
	cout << "请输入背包的载重（必须为整数，否则报错）：";
	cin >> t;
	assert(t > 0);                //背包载重大于零
	
	int *w;
	w = new int[n];
	assert(w != NULL);
	cout << "请依次输入各商品的重量（用空格隔开，同时必须为整数，否则报错）：\n";
	for (int i = 0; i < n; i++)
	{
		cin >> w[i];
		assert(w[i] > 0);          //商品重量大于零
	}
	
	bool flag = false;
	put(t, w, n, 0, flag);
	
	if (flag)
		cout << "可以恰好填满背包。";
	else cout << "不可以恰好填满背包。";
	cout << endl;
	
	delete[]w;
}