題目連結
https://www.luogu.com.cn/problem/P1064
解題思路
如果我們直接用動态規劃的模闆去處理的話，我們很難去處理選擇附件時的主件選擇；
我的一開始的思路是在輸入過程中把主件的值加到附件上，但由于每個主件的附件不唯一且主件可以單獨選擇，就很難處理；
後來換了一種思路，隻對主件進行處理：
·因為附件是依賴于主件的，是以我們可以在周遊主件時，對每個主件的附件進行選擇；
·在輸入的時候把值分成兩部分:main_w[]與attach_w[][]分别存儲主件與附件；
·attach_w[i][j]表示主件i的第j個附件的費用；
·這樣我們的狀态轉移方程就可以改為：
dp[j]=max(dp[j],dp[j-main_w[i]]+main_c[i]);
//選擇主件
if(j>=main_w[i]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][1]]+main_c[i]+attach_c[i][1]);
//選擇主件+第一個附件
if(j>=main_w[i]+attach_w[i][2])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]]+main_c[i]+attach_c[i][2]);
//選擇主件+第二個附件
if(j>=main_w[i]+attach_w[i][2]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]-attach_w[i][1]]+main_c[i]+attach_c[i][2]+attach_c[i][1]);
//選擇主件+兩個附件
代碼展示
#include<bits/stdc++.h>
using namespace std;
const int maxn=32005;
/*
思路:
6200
1500 7
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 0
400 4 0
怎麼能保證選擇一個附件之後
*/
int main_w[70];
int main_c[70];
int attach_w[70][3];
int attach_c[70][3];
int dp[maxn];
int rely[70][70];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(c!=0){
attach_w[c][0]++;
attach_w[c][attach_w[c][0]]=a;
attach_c[c][attach_w[c][0]]=a*b;
}
else {
main_w[i]=a;
main_c[i]=a*b;
}
}
//初始化
for(int i=1;i<=m;i++){
for(int j=n;main_w[i]!=0&&j>=main_w[i];j--){
dp[j]=max(dp[j],dp[j-main_w[i]]+main_c[i]);
if(j>=main_w[i]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][1]]+main_c[i]+attach_c[i][1]);
if(j>=main_w[i]+attach_w[i][2])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]]+main_c[i]+attach_c[i][2]);
if(j>=main_w[i]+attach_w[i][2]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]-attach_w[i][1]]+main_c[i]+attach_c[i][2]+attach_c[i][1]);
}
}
cout<<dp[n]<<endl;
return 0;
}