动态规划算法解背包问题.cpp

自己编写的

#include <iostream>
const int N = 100;
using namespace std;

int max(int a,int b)
{
	return (a > b ? a : b);
}


int main()
{
	int n;    // 物品总数
	int W;    // 背包总重量
	scanf("%d%d",&n,&W);
	int v[N]; // 存放各个物品的价值
	int w[N]; // 存放各个物品重量
	int f[N][N]; // 存放最终结果
	int flag[N]; // 标记数组，标记某个物品是否被选取
	int i,j;
	for(i = 0; i < n; i++)
		scanf("%d",&v[i]);
	for(i = 0; i < n; i++)
		scanf("%d",&w[i]);

	memset(flag,1,sizeof(flag)); // 标记数组赋初值

	// 初始化,只有一个物品的情况，也是边界
	for(j = 0; j <= w[0]-1; j++)
		f[0][j] = 0;
	for(j = w[0]; j <= W; j++)
		f[0][j] = v[0];
	
	for(i = 1; i < n; i++)
		for(j = 0; j <= W; j++)
			if(w[i] > j)
				f[i][j] = f[i-1][j];
			else
				f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
			
	printf("%d",f[n-1][W]);
	return 0;
}