题目

描述
在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A_{i}A
i
​

（每个物品只能选择一次）

样例

样例 1：
输入：
数组 = [3,4,8,5]
backpack size = 10
输出：
9
解释：
装4和5.

样例 2：
输入：
数组 = [2,3,5,7]
backpack size = 12
输出：
12
解释：
装5和7.

分析

物品不能分割，且每个物品只有一个，经典的01背包问题，直接二维状态数组，行代表承重，列代表第几个物品，值为bool类型，值为1时代表前i个物品可以组合成重量j。

1.最后一步

拿或者不拿当前这个物品能否正好凑出当前背包的承重，当前物品是第n个，不拿的时候看前n-1个物品可不可以凑出来这个承重，拿的时候看前n-1个物品能否凑出当前背包的承重减去当前物品的重量

2.转移方程

f[i][j]={f[i][j-1]||f[i-当前物品重量][j-1]}(i>=当前物品重量)

代码部分 1.初始化

f[0][j]=true 不拿物品的时候满足承重0
f[i][0]=false 不拿物品时一定凑不出来重量大于0的情况

    	int len=A.size();
    		//承重 第几个物品 
    	vector<vector<bool> > f(m+1,vector<bool>(len+1,false));	//状态 
    	f[0][0]=true;
		for(int i=1;i<=m;i++)		//初始化 
			f[i][0]=false;
		for(int i=1;i<=len;i++)
			f[0][i]=true;

2.动规核心

		int ans=0;	
		for(int i=1;i<=m;i++)		//动规核心 
		{
			for(int j=1;j<=len;j++)
			{
				f[i][j]=f[i][j-1];
				if(i>=A[j-1])
				{
					f[i][j]=f[i][j]||f[i-A[j-1]][j-1];
				}
				if(f[i][j])
					ans=i;
			}
		}

完整代码

class Solution {
public:
    int backPack(int m, vector<int> &A) {
    	int len=A.size();
    		//承重 第几个物品 
    	vector<vector<bool> > f(m+1,vector<bool>(len+1,false));	//状态 
    	f[0][0]=true;
		for(int i=1;i<=m;i++)		//初始化 
			f[i][0]=false;
		for(int i=1;i<=len;i++)
			f[0][i]=true; 

		int ans=0;	
		for(int i=1;i<=m;i++)		//动规核心 
		{
			for(int j=1;j<=len;j++)
			{
				f[i][j]=f[i][j-1];
				if(i>=A[j-1])
				{
					f[i][j]=f[i][j]||f[i-A[j-1]][j-1];
				}
				if(f[i][j])
					ans=i;
			}
		}
		
		return ans; 
    }
};

总结

背包问题，承重承重是一定要代入到状态中的，01背包问题，另一个维度代表的是第几个物品，如果是完全背包，另一个维度代表的就是拿几个物品，因为完全背包有多个同样的物品
这种方法tle了，稍后更新ac方法