1.(背包问题1)有一个质量上限为m的背包和n个物品。物品分三类，第一类物品有取的数量限制，第二类物品只能取一个,第三类物品可以无限取。

第i个物品的类别为tp[i](tp[i]∈[1,2,3])质量为w[i]，价值为c[i]，如果tp[i]=1 ，还会有一个a[0]表示这种物品最多只能取a[i]个。求这个背包可以装下的最大价值。

M≤1000,n ≤100,w[i],c[i]≤1000,a[i]<10,1≤tp[i]≤3。



试补全程序。

# include <iostream>


using namespace std;


int n, m, ans;


int f[100],a[101],tp[101],w[101],c[101];





int main() {


	cin>>m>>n;


	for(int i= 1; i<=n; ++i) {


		cin>> tp[i]>> w[i]>> c[i];


		if(tp[i] == 1) cin>> a[i];


	}


	f[0]= 0;


	for (int i= 1; i<= m; ++i)


		f[i]=___(1)___;


	for(int i= 1; i<=n; ++i) {


		if(tp[i]==1) {


			for (int j= 1; j<= a[i]; ++j)


				for(int v= m; v>=w[i]; --v)


					f[v] = max(f[v], ___(5)___ );


		}


		else if(tp[i]== ___(2)___) {


			for(int v=m; v>= ___(3)___ ; --v)


				f[v]=max(f[v], ___(5)___ );


		} 


		else {


			for( ___(4)___ )


				f[v]=max(f[v], ___(5)___ ) ;


		}


	}


	printf("%d", f[m]);


	return 0;


}

选择题