packetproblem.cpp

这是经典的背包问题

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

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

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

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

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

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

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

<学生姓名>:鲁鹏
*/

/*
	文件名称：	Proj1--背包问题
	项目名称：	PacketProblem
	创建者：	鲁鹏
	创建时间：	9/23/2006
	最后修改时间：9/24/2004
	功能：		判断背包问题是否有解

	文件中的函数名称和简单功能描述：无
	文件中定义的全局变量和简单功能描述：无
	文件中用到的他处定义的全局变量及其出处：无
	与其他文件的依赖关系：无
*/

#include<iostream>
using namespace std;

int main(){
	int n;
	cout<<"Please input the number of things: ";             //输入物品总数
	cin>>n;
	int *Weight=new int[n];                                  //动态申请重量的内存空间
	
	int Capacity;
	cout<<endl<<"Please input the capacity of bag: ";        //输入背包的载重量
	cin>>Capacity;
	int *sum=new int[Capacity+1];                            //sum[i]存储的是载重量为i时解法的个数，因此申请空间时必须空出一位sum[0]
	for (int i=0; i<(Capacity+1); i++)
		sum[i]=0;                                            //sum数组的初始化
	
	cout<<endl<<"Please input each thing's weight: ";        
	for (i=0; i<n; i++){                                     //依次输入每个物品的重量
		cin>>Weight[i];
		sum[Weight[i]]++;                                    //容量为 Weight[i] 的背包解法个数增加一
		for (int j=Capacity; j>=1; j--){                     //此步为动态规划对于每一次输入进行一次循环，从背包满负载向前尝试
			if ((Weight[i]+j) <= Capacity)                   //当已经容纳重量 j 的背包尚能容纳重量为 Weight[i] 的物品时
				sum[Weight[i]+j] += sum[j];                  //容量为 Weight[i]+j 的背包的解法的个数就等于容量为 j 的背包的解法个数
		}
	}
	cout<<endl;                                              //输入完毕，此时 sum[Capacity] 的值即是容量为 Capacity 的背包的解法的个数

	if (sum[Capacity])                                       //条件判断语句，只要解法不为零，则满足条件
		cout<<"This situation can be solved."<<endl;
	else
		cout<<"There are no solutions."<<endl;
	
	delete Weight;                                           //删除申请的内存空间
	delete sum;
	return 0;
}

/*
测试数据：
3
40
20
20
20

即有三件物品，背包容量为40，三件物品的重量分别为20、20、20
*/