动态规划——01背包问题

依然是一道来自实验报告的动态规划经典例题

• 问题描述
  给定n中物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量为c。问应该如何选择装入背包中的物品，使得装入背包的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。

• 问题分析
  首先确定子问题，我们采用一个二维数组m[][]来刻画，m[i][j]表示将前i个物品装入容量为j的背包中的最大价值。

初始状态为m[0][0−c]和m[0−n][0]都为0，前者表示前0个物品（也就是空物品）无论装入多大的包中总价值都为0，后者表示体积为0的背包啥价值的物品都装不进去。

当 j>=Wi 时，表明第i个物品可以装下，此时就可以选择装或者不装，装下的话m[i][j]=m[i+1][j-Wi]+Vi,不装的话m[i][j]=m[i+1][j]; 当j<Wi时，说明根本装不下第i个，所以m[i][j]=m[i+1][j]。

• 动态规划方程

• 图示填表过程
  比如一个价值数组v = { 5 ，6 ，5 ，1 ，19 ，7}，重量数组w = {2， 3 ，1， 4 ，6，5}

• 实现代码

#include <bits/stdc++.h>
using namespace std;
int max(int a,int b){
	if(a>b)
		return a;
	else
		return b;	
}
int main()
{
	int m[100][100]={0},v[100],w[100],n,c;
	int bag[100];	//	最优解 
	cin>>n;
	v[0]=0;
	for(int i=1;i<=n;i++)
		cin>>v[i];	//第i个物品的价值 
	w[0]=0;
	for(int i=1;i<=n;i++)
		cin>>w[i];	//第i个物品的重量
	cin>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			if(j<w[i]){
				m[i][j]=m[i-1][j];
			}
			else{
				m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
			}
		}
	}	 
	cout<<"最优值："<<m[n][c]<<endl;
    return 0;
}

该算法的时间复杂度为O（cn）；