題目背景
直達通天路·小A歷險記第二篇
題目描述
自01背包問世之后，小A對此深感興趣。一天，小A去遠游，卻發現他的背包不同于01背包，他的物品大致可分為k組，每組中的物品相互沖突，現在，他想知道最大的利用價值是多少。
輸入輸出格式
輸入格式：?
兩個數m,n，表示一共有n件物品，總重量為m
接下來n行，每行3個數ai,bi,ci，表示物品的重量，利用價值，所屬組數
?
輸出格式：?
一個數，最大的利用價值
?
輸入輸出樣例
輸入樣例#1：?復制
45 3
10 10 1
10 5 1
50 400 2 輸出樣例#1：?復制
10 說明
1<=m<=1000 1<=n<=1000 組數t<=100
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 1002 using namespace std; int n,m,k,ans; int dp[MAXN][MAXN]; int w[MAXN],v[MAXN],c[MAXN]; int dfs(int i,int j){if(dp[i][j]!=-1) return dp[i][j];if(i==n+1) return ans=0;if(j<w[i]||c[i]==c[i-1]) ans=dfs(i+1,j);else ans=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i]);return dp[i][j]=ans; } int main(){memset(dp,-1,sizeof(dp));cin>>m>>n;int i;for(i=1;i<=n;i++) cin>>w[i]>>v[i]>>c[i];cout<<dfs(1,m)<<endl; }
?
 方法)
)
