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;


}
0-N双肩包为题（动态规划算法）

相关推荐
