01背包.txt

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· 文本 代码 · 共 27 行

#include<iostream.h>
const maxn =  100 ;
const  maxm = 1000 ;//最大的重量

int main()
{
	int i ,j , m ,n,t;
	int w[maxn],v[maxn];
	int s[maxm] ;
	cout<<"请输入商品数和背包能装的重量"<< endl;
	cin>>n>>m ;
	cout<<"分别输入每个商品的价值和重量"<<endl;
	for(i = 0 ; i < n; i ++)
		cin>>v[i]>>w[i] ;
	for(i = 0 ; i <= m ; i ++)
		s[i] = 0;
	for(j = 1 ; j <= m ; j ++)
		for(i = 0 ; i < n ; i++)
			if(j - w[i] >=0)
			{
				t = s[j - w[i]] + v[i] ;
			    if(s[j]<t) s[j] = t ;
			}
			
    cout<<s[m]<<endl;
	return 1;
}