pack.cpp

背包问题(非0/1)C++标准算法

#include<iostream>
using namespace std;
int n,m;
int weight[10];
int v[10];
int f[10][10][2];
void Init()
{
	int i;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>weight[i];
	}
	for(i=0;i<n;i++)
	{
		cin>>v[i];
	}
}
void DP()
{
	int k,i,j;
	int temp;
	for(k=0;k<n;k++)
	{
		for(i=0;i<m;i++)
		{
			for(j=0;j<i/weight[k];j++)
			{
				if(k)temp=f[k-1][i-weight[k]*j][1]+v[k]*j;else temp=v[k]*j;
				if(f[k][i][1]<temp)
				{
					f[k][i][1]=temp;
					f[k][i][2]=j;
				}
			}
		}
	}
}
void Print(int k,int w)
{
	if(k<0)return;
	Print(k-1,w-weight[k]*f[k][w][2]);
	cout<<k<<" "<<f[k][w][2]<<endl;
}
void main()
{
	Init();
	DP();
	cout<<f[n-1][m][2]<<endl;
	Print(n-1,m);
}