backpack(int_dp).cpp

这是经典的背包问题

#include<iostream.h>

void main() {
	int n;   //n为物品总数
	int T;   //背包可容纳的总重量
	int w;   //临时记录当前物品重量的变量

	//以下为输入
	cout << "please input the number of things:" << endl;
	cin >> n;  //物品总数
	
    cout << "please input the overall weight that the backpack can put in:" << endl;
	cin >> T;  //输入背包可容纳的总重量

	double* t = new double[T + 1];  //建立数组,记录每个重量值的组合数

	t[0] = 1;
	for (int i = 1; i <= T; i ++) t[i] = 0;  //赋初值，注意t[0] = 1

	cout << "please input the weight of each thing:" << endl;
	
while(n --) {
		cin >> w;  //输入每件物品的重量,用临时变量w记录
		if (w <= T){
			for (i = T-w; i >= 0; i --) {
				if (t[i] != 0)  //对于t[i] != 0时，t[i + w]的组合数将增加t[i]种
					t[i + w] += t[i];
			}
		}
	}


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

	if (t[T] > 0)  //有解时,输出解个个数
		cout << "can do   " << t[T] << " methods" << endl;

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