hdu 3033 I love sneakers! (分组背包)

题目来源：点击打开链接

I love sneakers!

After months of hard working, Iserlohn finally wins awesome amount of scholarship. As a great zealot of sneakers, he decides to spend all his money on them in a sneaker store.

There are several brands of sneakers that Iserlohn wants to collect, such as Air Jordan and Nike Pro. And each brand has released various products. For the reason that Iserlohn is definitely a sneaker-mania, he desires to buy at least one product for each brand.
Although the fixed price of each product has been labeled, Iserlohn sets values for each of them based on his own tendency. With handsome but limited money, he wants to maximize the total value of the shoes he is going to buy. Obviously, as a collector, he won’t buy the same product twice.
Now, Iserlohn needs you to help him find the best solution of his problem, which means to maximize the total value of the products he can buy.

  
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66

  
255

题目意思： n个商品， V钱， K 个鞋子商标牌子 ， 每个商品有 商标，钱v, 价值money

求， 花所有的V钱，每种商标至少买一双鞋， 而且不重复买同样的鞋， 获得的最大价值

1：用vector 保存每一种商标的鞋子，然后对每一种商标进行讨论。

2：为了保证不重复购买同样的鞋， 钱（V）从大到小更新

3：dp[i][k] 表示买了（1,2，...，i）种款式的鞋子 ，使用k钱产生的最大价值。

dp[i][k] = Max(dp[i][k] , dp[i][k-v] + money , dp[i-1][k-v] + money)

代码如下：

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#define N 10005
#define Inf -0x7fffffff
using namespace std;
int dp[11][N];
int  K ,V;
struct Node
{int v;int money;
};
vector <Node > brand[11];
int Max(int a, int b, int c)  // 三个数求最大值， 这个函数好
{if(a<b)a=b;if(a<c)a=c;return a;
}
// 花所以的V（钱） 买所有种类的产品至少一种，且不重复购买同样产品
int DP()       
{int i,j,k;for(i=1; i<=K ; i++){if(brand[i].size() == 0)   // 不满足所有种类return Inf;}for(i=1 ; i<=K ;i++)// 初始化dpfor(j=0 ; j<=V ;j++)dp[i][j]=Inf;for(i=0; i<=V ;i++)dp[0][i]=0;   //for(i=1 ;i<=K ; i++)for(j=0 ; j< brand[i].size();j++){int v= brand[i][j].v;int money=brand[i][j].money;for(k=V ; k>=v ;k--)   // 钱从大到小dp[i][k]=Max(dp[i][k], dp[i][k-v]+money , dp[i-1][k-v]+money);}return dp[K][V];
}
int main()
{int n,i,k;Node node;while(cin>>n>>V>>K){for(i=1 ;i<=K ;i++)brand[i].clear();for(i=1 ; i<=n ;i++){cin>>k>>node.v>>node.money;brand[k].push_back(node);}if(DP() == Inf)puts("Impossible");elsecout<<dp[K][V]<<endl;}return 0;
}