bag4.cpp

这是经典的背包问题

// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
// 学生：朱诗雄

/*
	文件名称：	bag
	项目名称：	背包问题
	创建者：	朱诗雄
	文件中的函数名称和简单功能描述：
	void update(int now,int t,int *(&a));  该函数对数组a动态更新。
		

	输入格式：第一行输入背包重量t，第二行输入背包数量n，第三行输入每种物品的重量。
	输出格式：最后直接输出方法数。
	例：
	3
	5
	1 2 3 4 5
	输出：
	3
*/

#include<iostream>
using namespace std;

void update(int now,int t,int *(&a));

int main()
{
	int t;
	cin>>t;			//背包重量t
	int *a;
	a=new int [t+1];
	for(int i=0;i<=t;i++)
		a[i]=0;			//a[i]为背包容量为i时的放法总数,刚开始全为0
	int n,now;
	cin>>n;
	cin>>now;
	i=0;
	while(i<=t)
	{
		a[i]=1;
		i+=now;			//设第一个物品重的整数倍的重量值v，则将a[v]赋为1
	}
	for(i=1;i<n;i++)
	{
		cin>>now;
		update(now,t,a);	//更新数组a
	}
	cout<<a[t]<<endl;
	return 0;
}

void update(int now,int t,int *(&a))
{
	int *c;				//建立新数组的目的是防止下面的过程中，对数组a的重复计算
	c=new int [t];
	for(int j=0;j<=t;j++)
		c[j]=a[j];
	for(j=0;j<=t;j++)
		if(a[j]>0)
			for(int k=1;k<=t/now;k++)	//注意此处k不能等于0，否则会出现c[j]+=a[j]
				if( (j+now*k)<=t ) c[j+now*k]+=a[j];
	for(j=0;j<=t;j++)
		a[j]=c[j];	
}