reference:
6.4 knapsack in Algorithms(算法概论), Sanjoy Dasgupta University of California, San Diego Christos Papadimitriou University of California at Berkeley Umesh Vazirani University of California at Berkeley
the unbounded knapsack and 0-1 knapsack are both illuminatingly discussed in the reference book, in chapter 6 dynamic programming, strongly recommended. the multiple-choice knapsack and bounded knapsack are variants of 0-1 knapsack.
//
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXSIZE 105
int dp[MAXSIZE]={0}, *p;
int profit[MAXSIZE];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m,i,j,k;
while(scanf("%d%d",&n,&m)==2 && n>0 && m>0) {
memset(dp+1,0,(m+1)*sizeof(dp[0]));
for(i=0;i<n;++i) {
for(j=1;j<=m;++j) scanf("%d",&profit[j]);
/*
// 多重背包, unbounded knapsack
for(j=1;j<=m;++j) {
for(k=1;k<=j;++k) {
dp[j]=std::max(dp[j],profit[k]+dp[j-k]);
}
}*/
// 分组背包, multiple choice knapsack
for(j=m, p=dp+m;p!=dp;--p, --j) {
for(k=1;k<=j;++k) {
if(*p<profit[k]+p[-k])
*p=profit[k]+p[-k];
}
}
}
printf("%d
",dp[m]);
}
return 0;
}版权声明：本文为博主原创文章，未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.