本文主要是介绍hdu-3033-I love sneakers!--背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3033
本题解题思路：先把同样的号码放在一起，保证每一个号码的产品都能买到，计算 用钱能买到的物品的最大价值。
网络题解：
分组背包问题，大意**要买鞋，有k种牌子，每种牌子至少买一双鞋子。每双鞋子有标价跟实际价值。求用m多的钱买最多价值的鞋。
其实我觉得这题的难点就在处理“至少”这点上面。
状态方程很多都能推出用 dp[k][m] 来表示 已经买了k种鞋 在有m钱状态下的 鞋的最大价值。
状态转移方程为
for( k = 1 ; k <= K ; k++)
{
for( i = 0 ; i < num[k] ; i++)
{
for( j = mm ; j >= m[k][i].m ; j--)
{
if(dp[k][j - m[k][i].m] != -1)
dp[k][j] = Max(dp[k][j] , dp[k][j - m[k][i].m] + m[k][i].v);
if(dp[k-1][j - m[k][i].m] != -1 )
dp[k][j] = Max(dp[k][j] , dp[k-1][j - m[k][i].m] + m[k][i].v);
}
}
}
如果忽略了两个红色的判断句，大家都看得出这只是单纯的01背包且 没有条件限制，加了这两句就能实现至少了。理由如下
一开始我将dp[][]数组初始化为-1表示所有的数都不合法。大于0表示合法
然后将所有的 k = 0 dp[0][]置为0，这是为了 k = 1时能合法计算。
从状态方程中看出，当上一个状态值为-1时表示他不合法。所以当前状态没有计算的必要也不合法答案。
如果计算完第k类商品的取值后，所有的dp[k][]均为-1的时候，第k类表明没有一鞋被买。故所有状态都不合法，接下来的所有值也都将不合法。
在计算第k组商品的过程中，当某个-1变成一个非负数的时候，也就表明当前的第k种已经拿了第i件物品，所以变成合法答案了。
如此推下去，最后一个值dp[k][m],就是答案了。如果依然是-1，就输出impossible把。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;struct node
{int Money,weight;
}she[15][100005];int dp[105][10005];
int main()
{int N,M,K,a,b,c,num[20];while(scanf("%d%d%d",&N,&M,&K)!=EOF){memset(num,0,sizeof(num));for(int i=0;i<N;i++){scanf("%d%d%d",&a,&b,&c);she[a][num[a]].Money=b;she[a][num[a]].weight=c;num[a]++;}memset(dp,-1,sizeof(dp));for(int i=0;i<=M;i++){dp[0][i]=0;}for(int k=1;k<=K;k++)for(int i=0;i<num[k];i++)for(int j=M;j>=she[k][i].Money;j--){if(dp[k][j-she[k][i].Money]!=-1)dp[k][j]=max(dp[k][j],dp[k][j-she[k][i].Money]+she[k][i].weight);if(dp[k-1][j-she[k][i].Money]!=-1)dp[k][j]=max(dp[k][j],dp[k-1][j-she[k][i].Money]+she[k][i].weight);}if(dp[K][M]<0) printf("Impossible\n");else printf("%d\n",dp[K][M]);}
}
/*
5 13 3
1 2 3
1 4 6
2 10 2
3 2 2
3 1 2
*/
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 130 0 0 0 0 0 0 0 0 0 0 0 0 0 01 -1 -1 3 3 6 6 9 9 9 9 9 9 9 92 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 53 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7
*/
这篇关于hdu-3033-I love sneakers!--背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
