本文主要是介绍hdu 3033 I love sneakers! (分组背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：点击打开链接
I love sneakers!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3493 Accepted Submission(s): 1425
Problem Description
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.
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.
Input
Input contains multiple test cases. Each test case begins with three integers 1<=N<=100 representing the total number of products, 1 <= M<= 10000 the money Iserlohn gets, and 1<=K<=10 representing the sneaker brands. The following N lines each represents a product with three positive integers 1<=a<=k, b and c, 0<=b,c<100000, meaning the brand’s number it belongs, the labeled price, and the value of this product. Process to End Of File.
Output
For each test case, print an integer which is the maximum total value of the sneakers that Iserlohn purchases. Print "Impossible" if Iserlohn's demands can’t be satisfied.
Sample Input
5 10000 3 1 4 6 2 5 7 3 4 99 1 55 77 2 44 66
Sample Output
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;
}
这篇关于hdu 3033 I love sneakers! (分组背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
