0-1背包 动态规划求解问题（学习笔记）

问题描述

现有四个物品，小偷背包容量为8，怎么可以偷得价值最多的物品？

物品信息如下：

物品编号	1	2	3	4
物品重量	2	3	4	5
物品价值	3	4	5	8

记F(k,w),即可以偷前k件物品，背包容量为w下所能偷到的最大价值

以F(4,8)为例

 状态转移方程为：

	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1：（w=2，v=3）	0	0	3	3	3	3	3	3	3
2：（w=3，v=4）	0	0	3	4	4	7	7	7	7
3：（w=4，v=5）	0	0	3	4	5	7	8	9	9
4：（w=5，v=8）	0	0	3	4	5	8	8	11	12

#include 
#include 
#include  //memset的头文件

using namespace std;

int F[5][9]={0};
int w[5]={0,2,3,4,5};
int v[5]={0,3,4,5,8};

int main()
{
    memset(F,0,sizeof(F));
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=8;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]);
            }
        }
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=8;j++)
        {
            cout<<"F["< 
 
学习视频：
 
动态规划DP0-1背包_哔哩哔哩_bilibili算法：动态规划01背包https://www.bilibili.com/video/BV1g7411B7SP?spm_id_from=333.337.search-card.all.click