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\n",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.