題目鏈接: acm.hdu.edu.cn/showproblem.php?pid=1712

分析: 這是一個(gè)01背包的變體 ,但始終是01背包,只不過(guò), 每 個(gè)物體的代價(jià)和 利益的狀態(tài)不唯一(也就是說(shuō)花費(fèi)不同的代價(jià) 得到不同的利益 ) . 所以只要在最里面再加一 層循環(huán),遍歷 每個(gè)物體的不代價(jià)和利益的狀態(tài) 即可!

?

    #include<iostream>

#include<string>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<iomanip>



using namespace std;

const int maxn=100000;



int map[105][105];

int dp[102];



int main(){

    int n,m;

    while(cin>>n>>m,n||m){

        for(int i=1;i<=n;++i)

            for(int j=1;j<=m;++j)

                cin>>map[i][j];

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;++i)

            for(int k=m;k>=1;--k)

                for(int j=1;j<=k;++j){

                    if(dp[k]<dp[k-j]+map[i][j])

                        dp[k]=dp[k-j]+map[i][j];

                }

        cout<<dp[m]<<endl;

    }

    return 0;

}








  

?

?

HDU 1712 01背包 ACboy needs your help