/*
我真誠地保證
我自己獨立地完成了整個程序從分析、設計到編碼的所有工作。

如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序實習報告中
詳細地列舉我所遇到的問題，以及別人給我的提示。

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

我都已經在程序的注釋里很清楚地注明了引用的出處。

我從未抄襲過別人的程序，也沒有盜用別人的程序，

不管是修改式的抄襲還是原封不動的抄襲。

我編寫這個程序，從來沒有想過要去破壞或妨礙其他計算機系統的正常運轉。

學號：00548250 
姓名：卞超軼

*/

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

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";
	int i, j;
	for (i = 0; i < n; i++)
	{
		cin >> w[i];
		assert(w[i] > 0);       //商品重量大于零
	}
	
	int *s;
	s = new int[t+1];
	assert(s != NULL);
	for (i = 0; i <= t; i++)
		s[i] = 0;
	s[0] = 1;                 //申請動態數組并初始化
	                          //s[i]用來標記背包載重為i時能否恰好裝滿

	for (i = 0; i < n; i++)       //外層循環控制商品個數
		for (j = t; j >= w[i]; j--)     //內層循環尋找有解的背包   
			if (s[j-w[i]] != 0)  
				s[j] = 1;             //如果載重為（j-w[i]）的背包有解，那么載重為j的背包有解
	 
	if (s[t] != 0)
		cout << "可以恰好填滿背包。";
	else cout << "不可以恰好填滿背包。";
	cout << endl;
	
	delete[]w;
	delete[]s;
}