01背包问题-HJ16 购物单

 牛客测试地址，01背包
 1 动态规划

class Solution{
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        int dp[n+1][V+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=V;j++){
                dp[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=V;j++){
                int space=vw.at(i-1).at(0);
                int w=vw.at(i-1).at(1);
                if(j>=space){
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-space]+w);
                }else{
                   dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n][V];
    }
};

 另外一个实例，HJ16 购物单

#include<iostream>
#include<math.h>
#include <vector>
#include <map>
#include <array>
using namespace std;
struct Good{
    Good():price(0),utility(0){}
    Good(int a,int b):price(a),utility(b){}
    int num=0;
    int price;
    int utility;
};
void configTest(int &N,int &m,std::vector<std::array<Good,4> >& goods,int factor=10){
    N=1000/factor;
    m=5;
    goods.resize(m);
    std::vector<std::vector<int>> vpq;
    vpq.push_back({800,2,0});
    vpq.push_back({400,5,1});
    vpq.push_back({300,5,1});
    vpq.push_back({400,3,0});
    vpq.push_back({500,2,0});
    for(int i=0;i<vpq.size();i++){
        int price=vpq.at(i).at(0)/factor;
        int weight=vpq.at(i).at(1);
        int index=i;
        int j=0;
        if(0!=vpq.at(i).at(2)){
            index=vpq.at(i).at(2)-1;
            j=1;
            if(1==goods[index].at(j).num){
                j=2;
            }
        }
        goods[index].at(j).num=1;
        goods[index].at(j).price=price;
        goods[index].at(j).utility=(price*weight);
    }
}
static inline int getArrsize(std::array<Good,4>&arr){
    int ret=0;
    if(0==arr.at(0).num){
        ret=0;
    }else if(0==arr.at(1).num){
        ret=1;
    }else if(0==arr.at(2).num){
        ret=2;
    }else if(0==arr.at(3).num){
        ret=3;
    }else{
        ret=4;
    }
    return ret;
}
void processData(std::vector<std::array<Good,4> > &goods){
    std::vector<std::array<Good,4> > buffer;
    int n=goods.size();
    for(int i=0;i<n;i++){
        int sz=getArrsize(goods.at(i));
        if(sz>0){
            buffer.push_back(goods.at(i));
        }
    }
    goods.swap(buffer);
}
int main(){
    int N,m;
    int factor=10;
    std::vector<std::array<Good,4> > goods;
    //configTest(N,m,goods);
    {
        std::cin>>N;
        std::cin>>m;
        goods.resize(m);
        N/=factor;
        int v,p,q;
        for(int i=0;i<m;i++){
            std::cin>>v;
            std::cin>>p;
            std::cin>>q;
            int index=i;
            int j=0;
            if(q!=0){
                index=q-1;
                j=1;
                if(0!=goods.at(index).at(j).num){
                    j=2;
                }
            }
            goods.at(index).at(j).num=1;
            int price=v/factor;
            goods.at(index).at(j).price=price;
            goods.at(index).at(j).utility=price*p;
        }
    }
    processData(goods);
    int all=goods.size();
    int dp[all+1][N+1];
    for(int i=0;i<=all;i++){
        for(int j=0;j<=N;j++){
            dp[i][j]=0;
        }
    }
    for(int i=1;i<=all;i++){
        for(int j=1;j<=N;j++){
            int buy=0;
            int sz=getArrsize(goods.at(i-1));
            int max_u=dp[i-1][j];
            if(1==sz){
                buy=0;
                int a=goods.at(i-1).at(buy).price;
                int b=goods.at(i-1).at(buy).utility;
                if(j>=a){
                   max_u=max(max_u,dp[i-1][j-a]+b);
                }
            }else if(2==sz){
                buy=0;
                int a=goods.at(i-1).at(buy).price;
                int b=goods.at(i-1).at(buy).utility;
                buy=1;
                int c=goods.at(i-1).at(buy).price;
                int d=goods.at(i-1).at(buy).utility;
                if(j>=a){
                    max_u=max(max_u,dp[i-1][j-a]+b);
                }
                if(j>=a+c){
                    max_u=max(max_u,dp[i-1][j-a-c]+b+d);
                }
            }else if(3==sz){
                buy=0;
                int a=goods.at(i-1).at(buy).price;
                int b=goods.at(i-1).at(buy).utility;
                buy=1;
                int c=goods.at(i-1).at(buy).price;
                int d=goods.at(i-1).at(buy).utility;
                buy=2;
                int e=goods.at(i-1).at(buy).price;
                int f=goods.at(i-1).at(buy).utility;
                if(j>=a){
                    max_u=max(max_u,dp[i-1][j-a]+b);
                }
                if(j>=a+c){
                    max_u=max(max_u,dp[i-1][j-a-c]+b+d);
                }
                if(j>=a+e){
                    max_u=max(max_u,dp[i-1][j-a-e]+b+f);
                }
                if(j>=a+c+e){
                    max_u=max(max_u,dp[i-1][j-a-c-e]+b+d+f);
                }
            }
            dp[i][j]=max_u;
        }
    }
    std::cout<<factor*dp[all][N];
}

Reference:
[1] 算法分享之01背包问题
[2]动态规划---01背包问题详解
[3]动态规划：01背包问题