背包dp

P1064 [NOIP2006 提高组] 金明的预算方案

思路：有依赖的背包。主要的问题和解决方案,见代码注释.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N=2e5+10;

typedef struct node{
    int p,w,typ;
}node;
bool cmp(node a,node b){
    if(a.typ!=b.typ) return a.typ<b.typ;
    return a.p<b.p;
}
int money,n;
int dp[40000];     ////dp[j] 定义为:花费j钱，最多可以得到的满意度
vector<node> vct[65];
void solve(){                       ////有依赖的背包
    cin>>money>>n;
    for(int i=1;i<=n;i++){
        node x; cin>>x.p>>x.w>>x.typ;
        if(x.typ==0) vct[i].emplace_back(x);
        else vct[x.typ].emplace_back(x);
    }
    for(int i=1;i<=n;i++) sort(vct[i].begin(),vct[i].end(),cmp);
    for(int i=1;i<=n;i++){            ////枚举主件.
        for(int j=money;j>=0;j-=10){
            if(vct[i].empty()) continue;
            int num=(int)vct[i].size();
            for(int g=0;g<(1ll<<(num-1));g++){ ////这里是<,不能是<= ////二进制枚举该主件的附件的选取状况---有很关键的一句话:每个主件只会有0,1,2个附件.所以这里不会很大.
                int p=vct[i][0].p;
                int v=vct[i][0].p*vct[i][0].w;
                for(int h=0;h<num-1;h++){
                    if((1ll<<h)&g){
                        p+=vct[i][h+1].p;
                        v+=vct[i][h+1].p*vct[i][h+1].w;
                    }
                }
                if(j>=p) dp[j]=max(dp[j],dp[j-p]+v);        ////在这个主件中，总是先更新大的j，再更新小的j
                ////for(int j=money;j>=p;j--) dp[j]=max(dp[j],dp[j-p]+v);         ////在该状态下的p和v
                ////在这里枚举金钱的话,可能导致同一个主件的不同附件状态多次更新答案,这是不行的.
                ////在某一个主件的集合中，只能从中选取一次。答案不能被同一个集合重叠更新。意思是:假如取了主件1和附件1，那么取了主件1和附件2就不能从取主件1和附件1转移过来.
                ////这是个最严重的问题，重叠更新了！！---解决方案:在枚举这个主件中，只能先更新大的j，再更新小的j。否则同一个主件中小的j会更新同一个主件大的j
            }
        }
    }
    cout<<dp[money];
}
////带有前提条件:
////在考虑附件的时候，怎么转移呢？怎么知道它的主件是否购买了？a主件和b主件同时购买了是什么状态？只购买了a主件又是什么状态？
////这个题的决策是五个，分别是：
////1.不选，然后去考虑下一个
////2.选且只选这个主件          ////怎么转移呢,如果选了这个主件是亏的，但是附件可以转亏为盈呢..---在主件选了的情况下，二进制枚举附件的状态即可.
////3.选这个主件，并且选附件1
////4.选这个主件，并且选附件2
////5.选这个主件，并且选附件1和附件2.
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}