题目大意

食品的体积就是01背包问题中的体积 也就是 w 数组

食品的所含卡路里就是01背包问题中的价值 也就是 v 数组

所以这就是一道 01背包问题 的模板题

题目分析

使用dp 套01背包的模板

01背包问题的模板

状态转移方程

01背包的状态转移方程为

f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[j])

i 代表对 i 件物体做决策，有两种方式:

1.放入背包

2.不放入背包。

j 表示当前背包剩余的容量。

转移方程的解释：
创建一个状态矩阵 f ，横坐标 i 是物体编号，纵坐标 j 为背包容量。
首先将 f 第 0 行和第 0 列初始化为 0

注意:代码里面将整个 f 初始化为 0 了，其实只初始化第 0 行和第 0 列就够了 这个表示不放物体时最大价值为 0 。物体编号从 1 开始
接下来依次遍历 f 的每一行

如下所示

for (int i = 1; i <= n; i++)
{
	for (int j = V; j >= 0; j--) //所有的背包大小
	{
		if (j >= w[i]) //如果背包装得下当前的物体
		{
			f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
		}
		else //如果背包装不下当前物体
		{
			f[i][j] = f[i - 1][j];
		}
	}
}

01背包问题正解

#include<bits/stdc++.h> 
using namespace std;
 
int dp(int n, int m, int v[], int w[])
{
	int f[1000][1000];
	for (int i = 0;i <= n;i++)
		f[i][0] = 0;
	for (int j = 0;j <= n;j++)
		f[0][j] = 0;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 0;j <= m;j++)
		{
			if (j < w[i])
				f[i][j] = f[i - 1][j];
			else
			{
				f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
			}
 
		}
	}
	return f[n][m];
 
}
int main()
{
	int n, m, v[101], w[101];
	cin >> n >> m;//n为物品个数，m为背包容量，w为物品重量，v为物品价值 
	for (int i = 1;i <= n;i++)
	{
		cin >> w[i] >> v[i];
	}
 
	cout << dp(n, m, v, w);
	return 0;
}

转换到这道题的做法就是:

当这个物品能取时，也就是 j >= v [ i ]&& k >= w [ i ]时

f [ i ][ j ][ k ]= max ( f [ i-1 ][ j ][ k ], f [ i-1 ][ j-v[i] ][ k-w[i] ]);

否则

f [ i ][ j ][ k ]= f [ i-1 ][ j ][ k ];

谁抄袭啊? 逊

完整代码

#include<bits/stdc++.h> 
using namespace std;

//n为物品个数 
int n;

//背包 物品
struct node
{
    int V;
    int T;
    int KaLuLi;
};

//背包
int Vv,Ww;

//物品
node w[524];

//dp数组
int f[500][500][500];


void dp()
{


    //计算
	for(int i=1;i<=n;i++)
    {   
		for(int j=Vv;j>=0;j--)
        {
			for(int k=Ww;k>=0;k--)
            {
				if(j>=w[i].V&&k>=w[i].T)
                {
                    f[i][j][k]=max(f[i-1][j][k],f[i-1][j-w[i].V][k-w[i].T]+w[i].KaLuLi);
                }
					
				else
                {
                    f[i][j][k]=f[i-1][j][k];
                } 
			}
		}
	}
	cout<<f[n][Vv][Ww]<<endl;
 
}
int main()
{
	//体积最大值和质量最大值
    cin>>Vv>>Ww; 

    //食品总数
    cin>>n;

    //物品信息
	for(int i=1;i<=n;i++)
	{
		cin>>w[i].V>>w[i].T>>w[i].KaLuLi;
	}
 
	dp();


	return 0;
}