背包问题扩展一.cpp

这是经典的背包问题

#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 的背包的解法的个数

	cout<<"There are "<<sum[Capacity]<<" solutions."<<endl;  //直接输出解法的个数
	
	delete Weight;
	delete sum;
	return 0;
}

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

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