HJ16 购物单

输入：
  1000 5
  800 2 0
  400 5 1
  300 5 1
  400 3 0
  500 2 0
输出：2200

输入：
  50 5
  20 3 5
  20 3 5
  10 3 0
  10 2 0
  10 1 0
输出：130
说明：
由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130    

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main(){
    int N,m;//N：总钱数  m：可以购买的物品数
    cin>>N>>m;
    vector<vector<int>> prices(m+1,vector<int>(3,0));//价格  （m+1,3）  其中vector<int>(3)中[0]表示主件，[1]、[2]表示附件
    vector<vector<int>> values(m+1,vector<int>(3,0));//价值   ：价格*重要程度
    N/=10;//由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a/=10;
        b*=a;
        if(c==0){//主件
            prices[i][0]=a;
            values[i][0]=b;
        }else{//附件
            if(prices[c][1]==0){
                prices[c][1]=a;
                values[c][1]=b;
            }else{
                prices[c][2]=a;
                values[c][2]=b;
            }
        }
    }
    //使用分组背包
    vector<vector<int>> dp(m+1,vector<int>(N+1));
    for(int i=1;i<=m;i++){
        for(int j=1;j<=N;j++){
            int a=prices[i][0],b=values[i][0];
            int c=prices[i][1],d=values[i][1];
            int e=prices[i][2],f=values[i][2];
            dp[i][j]=j>=a?max(dp[i-1][j-a]+b,dp[i-1][j]):dp[i-1][j];
            dp[i][j]=j>=(a+c)?max(dp[i-1][j-a-c]+b+d,dp[i][j]):dp[i][j];
            dp[i][j]=j>=(a+e)?max(dp[i-1][j-a-e]+b+f,dp[i][j]):dp[i][j];
            dp[i][j]=j>=(a+c+e)?max(dp[i-1][j-a-c-e]+b+d+f,dp[i][j]):dp[i][j];
        }
    }
    cout<<dp[m][N]*10<<endl;
}