0-N背包為題（動態規劃算法），0-n為題

0-N背包為題（動態規劃算法），0-n為題

/****************0-N背包問題******************
 * 有n個物體裝入容量為c的背包，每一個物體有一個體積
 * 和一個價值，所裝入的物體體積之和不大於背包體積，
 * 且每個物體可以多次裝入，即每個物體有很多個（與0-1
 * 背包問題的區別），求裝入的最大價值？
 * *****************************************/
/********************************************
 * Author:ChengSong
 * Time:2015/12/29 22:24
 * language:C++
 * alogrithm: Dynamic Programing(動態規劃)
 * *****************************************/
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
int knapsack0N(int goodsnum,int capacity,int *weight,int *value,int **result,int *count){
    for(int i=0;i<goodsnum+1;++i)result[i][0] = 0;//容量為0的時候result[i][0] =0
    for(int j=0;j<capacity+1;++j)result[0][j] = 0;//沒有物體時候result[0][j] = 0
    /*遞歸求解結果集result*/
    for(int i=1;i<goodsnum+1;++i)
        for(int j=1;j<capacity+1;++j)
        {
            if(weight[i]>j){//當第i個物體的重量weight[i]大於背包重量j時
                result[i][j] = result[i-1][j];
            }
            else{//當物體的重量小於等於背包重量時
                int max_k = j/weight[i];//max_k為當前背包容量為j時最多可裝入物體i的個數
                int t = result[i-1][j];
                for(int k=1;k<max_k+1;++k){//循環求解出result[i-1][j]與result[i-1][j-k*weight[i]]+k*value[i]的最大的一個（k=1...max_k）
                    if(t<result[i-1][j-k*weight[i]]+k*value[i]){
                        t = result[i-1][j-k*weight[i]]+k*value[i];
                    }
                }
                result[i][j] = t;//當前t 為result[i-1][j]與result[i-1][j-k*weight[i]]+k*value[i]的最大的一個(k=1...max_k)
            }
        }
    return result[goodsnum][capacity];//返回最後結果:容量為capacityd背包裝入goodsnum種物體的最大值
}

int main(){
    int goodsnum,capacity;//物體個數與背包容量
    cin>>goodsnum>>capacity;
    int *count = new int[goodsnum+1];
    for(int i=0;i<goodsnum+1;++i)
        count[i] = 0;//每個物體放入的個數，初始化為0
    int *weight = new int[goodsnum+1];
    int *value = new int[goodsnum+1];
    int **result = new int*[goodsnum+1];//結果集，result[i][j]表示有i類物體放入容量為j的背包內的最大價值
    for(int i=0;i<goodsnum+1;i++)
        result[i] = new int[capacity+1];
    for(int i=1;i<goodsnum+1;++i){
        cin>>weight[i]>>value[i];
    }
    cout<<knapsack0N(goodsnum,capacity,weight,value,result,count)<<endl;
    /*該循環用來計算每個物體裝入的個數*/
    for(int i=goodsnum;i>0;){
        if(result[i][capacity]==result[i-1][capacity])//該條件下物體i不裝入，count[i]不變，i--
            i--;
        else{
            //該條件下物體i可以裝入數目增加一個,i不變，在進入循環，看看i物體是否還能在裝入
            count[i]++;
            capacity -= weight[i];
        }
    }
    //將裝入個數不為0的物體輸出，並輸出該物體裝入的個數
    for(int i=1;i<goodsnum+1;i++){
        if(count[i]!=0)
            cout<<i<<" "<<count[i]<<endl;
    }
    return 0;


}