01背包问题

有关01背包的详细介绍在这就不介绍了，仅给出算法模板

//写在前面
//01问题：有N个物品，每个物品都有其对应的体积和价值
//有一个容量为V的背包问怎样放能使背包中物品的价值最大
//状态转移方程为：f[i][v]=max(f[i-1][v],f[i-1][v-a[i]+b[i]) 
//当使用空间优化是状态转移方程为：f[v]=max(f[v],f[v-a[i]]+b[i]) 
#include <iostream>
#include <string.h>
#define maxn 1000
using namespace std;
int N,V;//分别代表物品的数量和背包的容量 
int a[maxn];int b[maxn];//分别代表物品的体积和价值 
int ans[maxn];//dp数组 
int main()
{
    cin>>N>>V;
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=N;i++)cin>>a[i]>>b[i];
	
	for(int i=1;i<=N;i++)
	{
		for(int j=V;j>=0;j--)
		if(j>=a[i]){ans[j]=max(ans[j],ans[j-a[i]]+b[i]);}//状态转移方程 
	}
	
	for(int i=1;i<=V;i++)cout<<ans[i]<<\' \';
} 
/*
5 10
2 6
2 3
6 5
5 4
4 6
*/