题目链接:Click here~~
题意:
有n门课,最多学习M天。A[i][j]表示学习第 i 门课 j 天得到的价值。求如何使价值最大。
解题思路:
最裸分组背包。把每一天看做一组,每组中还有M件物品,只能不选或者选择其中一个物品。
然后依次对每组进行01背包。
一定要注意在dp时的三层循环的顺序。
for(V->0)这层循环必须在for(所有属于 i 组的物品)外。这样才能保证每一组内的物品最多只有一个放入背包。
#include <stdio.h> #include <string.h> #define max(a,b) a > b ? a : b #define N 103 int main() { int n,V,w[N][N],dp[N]; while(scanf("%d%d",&n,&V),n||V) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=V;j++) scanf("%d",&w[i][j]); for(int i=1;i<=n;i++) //All the group for(int j=V;j>=1;j--) //Volume of the Bag for(int k=j;k>=1;k--) //Goods of the group dp[j] = max(dp[j],dp[j-k]+w[i][k]); printf("%d\n",dp[V]); } return 0; }