[文章目录]
Description
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
分组背包，借用上一组DP值就可以了（技巧： 二维数组，0^1=1,1^1=0）
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,v,t;
int f[210][2];
struct node
{
int w[40],val[40];
int size;
}id[20];
int main()
{
scanf("%d%d%d",&v,&n,&t);
for(int x,y,z,i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
int t=++id[z].size;
id[z].w[t]=x;
id[z].val[t]=y;
}
int c=1;
for(int i=1;i<=t;i++)
{
for(int j=1;j<=id[i].size;j++)
{
int ww=id[i].w[j],vv=id[i].val[j];
for(int k=v;k>=ww;k--)
{
f[k][c]=max(f[k][c],f[k-ww][c^1]+vv);
}
}
for(int i=v;i>0;i--)
f[i][c]=max(f[i][c],f[i][c^1]);
c=c^1;
}
printf("%d",f[v][c^1]);
return 0;
}