动态规划-01背包问题

• 大佬整理的理解链接：(建议先看一遍自行理解DP思想再去看代码）

动态规划之01背包问题 - kkbill - 博客园01背包问题 问题描述： 给定 n 件物品，物品的重量为 w[i]，物品的价值为 c[i]。

现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总https://www.cnblogs.com/kkbill/p/12081172.html

• 思路 

DP算法核心思想： 过利用已有的子问题信息高效求出当前问题的最优解。

    f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少。

    result=max(f[n][0~v]) 
    
    f[i][j]:
    （1）、不选第i个物品，f[i][j]=f[i-1][j];
    理解：不选第i个物品有两种情况：
        a. 体积不够
        b. 不是最优解，即f[i-1][j]为优解
   （ 2）、选择第i个物品，f[i][j]=f[i-1][j-v[i]]+w[i]
    理解：这里用到了以前已经解决了的子问题，即f[i-1][j-v[i]]的最优解 
    
    eg：新加的物品体积为2，价值为4，假设体积够装,则f[i][j]=max(f[i-1][j-2]+4,f[i-1][j]) 
        如果体积不够装，则f[i][j]=f[i-1][j] 
        
    f[j]:
    状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i]） 。

(我在题目中用f1[N]来表示优化后的一维数组)

代码：

#include
#include
using namespace std;

const int N=1010;

int n,m; 
int f[N][N];	//i个物品在总体积小于等于j的情况下可以获得的最大价值 
int v[N],w[N];	//分别表示第i个物品的体积和价值 
int f1[N];		//优化的一维版数组 


//二维版 
int main()
{
	cin>>n>>m;	//背包里有n个东西，能装的物品的体积总和不超过m
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; 
	
	//全局变量初始值默认为0，此步骤可省略
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			//不选择第i个物品
			f[i][j]=f[i-1][j];
			//选择第i个物品
			if(j>=v[i]) //当前背包的体积可以装下第i个物品
			{
				f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
			} 
		} 
		
	//f[n][m]即为最大值	
	cout<>n>>m;
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
	
	for(int i=1;i<=n;i++)
		for(int j=m;j>=v[i];j--)
			f1[j]=max(f1[j],f1[j-v[i]]+w[i]);
	
	cout<