动态规划学习——背包问题

问题：

有一个背包，有最大的可以承受的重量Weight
有一些物品，每个物品都有相应的重量和价值
给两个数组w[]和v[]，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值
求如何拿才能在不超过背包承重的情况下拿到的最大价值

问题分析：
对于每一个物品都有“拿”和“不拿”两个选项
在对第i个物品做出选择的时候：
若选择拿，则结果为“在对第i+1个物品做出拿或不拿选择获得的最大价值加上该物品的价值”，并且此时背包的剩余重量要减去该物品重量
若选择不拿，则结果为“在对第i+1个物品做出拿或不拿选择获得的最大价值”，且此时背包剩余质量不用减去该物品的重量
?

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int Weight=0;//背包最大承重
int N;//物品总数
int w[1000],v[1000];
int ways2_temp[10000][10000];

//法一 直接递归
int ways1(int index,int restWeight)
{
    if(restWeight<0) return -1; //如果剩余空间为负，则不能拿
    if(index==N) return 0; //递归出口，所有的物品都已经考虑完了
    int t1=ways1(index+1,restWeight);
    int t2=0;
    int next=ways1(index+1,restWeight-w[index]);//拿了该物品后，可能剩余空间为负的，即该物品装不下，所以需要判断是否能拿该物品，如果不能即返回-1则不能拿
    if(next!=-1){
        t2=v[index]+next;//拿完该物品后剩余空间不为负，才可以拿该物品
    }
    return max(t1,t2);
}

//法二：动态规划
int ways2()
{
    int index,restWeight;//index为当前扫描数组到达的索引，restWeight为背包剩余的容量
    for(restWeight=0;restWeight<=Weight;restWeight++) ways2_temp[N][restWeight]=0; //递归的出口，也是动态规划的开始，即从数组的最后一排开始向上填充数组
    //根据直接递归的依赖条件来填充动态规划数组
    for(index=N-1;index>=0;index--){
        for(restWeight=0;restWeight<=Weight;restWeight++){
            int p1=ways2_temp[index+1][restWeight];
            int p2=0;
            int next=restWeight-w[index]<0?-1:ways2_temp[index+1][restWeight-w[index]];
            if(next!=-1) p2=v[index]+next; 
            ways2_temp[index][restWeight]=max(p1,p2);
        }
    }
    return ways2_temp[0][Weight];
}

int main()
{
    cout<<"请输入背包最大承重"<<endl;
    cin>>Weight;
    cout<<"请输入物品总数";
    cin>>N;
    int i,j;
    cout<<"请按顺序输入物品的重量"<<endl;
    for(i=0;i<N;i++) cin>>w[i];
    cout<<"请按顺序输入物品的价值"<<endl;
    for(i=0;i<N;i++) cin>>v[i];
    int result1=ways1(0,Weight);
    cout<<"直接递归的结果为 "<<result1<<endl;
    int result2=ways2();
    cout<<"动态规划的结果为 "<<result2<<endl;

    return 0;
}

参考资料：

bilibili 马士兵教育——左程云

【应B友要求火速上线！算法大神（左程云）教你从暴力递归到动态规划，吊打所有暴力递归、动态规划问题】https://www.bilibili.com/video/BV1ET4y1U7T6?p=13&vd_source=4e9b7dd8105df854ae96830c97920252