题意：给你 n，m，k，表示有k种鞋子共n双，你有m的容量；
每双鞋子有容量p和价值v；问是否买全k种鞋子，若能在容量为m的情况下最多能买到鞋子的价值为多少；
每双鞋子只能买一次（01背包），每种鞋子至少买一种（分组背包：每组只能有一个）与传统分组背包的限制相反。
注意初始化！！！
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define maxn 127 #define PI acos(-1.0) struct node { int v,p; }f[11][10005]; int main() { int n,m,k; int dp[11][10005]; while(~scanf("%d%d%d",&n,&m,&k)) { int i,j; int a,b,c; int kao[15]; memset(kao,0,sizeof(kao)); memset(f,0,sizeof(f)); for(i=0;i =f[i][h].p;j--) { if(dp[i][j-f[i][h].p]!=-1)//由当前状态转移 dp[i][j]=max(dp[i][j],dp[i][j-f[i][h].p]+f[i][h].v); if(dp[i-1][j-f[i][h].p]!=-1)//由上一状态转移 dp[i][j]=max(dp[i][j],dp[i-1][j-f[i][h].p]+f[i][h].v); } } } if(dp[k][m]==-1) printf("Impossible\n"); else printf("%d\n",dp[k][m]); } return 0; } /* 5 10 3 1 4 6 2 5 7 3 4 99 1 55 77 2 44 66 */