/****************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=;i<goodsnum+;++i)result[i][] = ;//容量为0的时候result[i][0] =0
for(int j=;j<capacity+;++j)result[][j] = ;//没有物体时候result[0][j] = 0
/*递归求解结果集result*/
for(int i=;i<goodsnum+;++i)
for(int j=;j<capacity+;++j)
{
if(weight[i]>j){//当第i个物体的重量weight[i]大于背包重量j时
result[i][j] = result[i-][j];
}
else{//当物体的重量小于等于背包重量时
int max_k = j/weight[i];//max_k为当前背包容量为j时最多可装入物体i的个数
int t = result[i-][j];
for(int k=;k<max_k+;++k){//循环求解出result[i-1][j]与result[i-1][j-k*weight[i]]+k*value[i]的最大的一个（k=1...max_k）
if(t<result[i-][j-k*weight[i]]+k*value[i]){
t = result[i-][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+];
for(int i=;i<goodsnum+;++i)
count[i] = ;//每个物体放入的个数，初始化为0
int *weight = new int[goodsnum+];
int *value = new int[goodsnum+];
int **result = new int*[goodsnum+];//结果集，result[i][j]表示有i类物体放入容量为j的背包内的最大价值
for(int i=;i<goodsnum+;i++)
result[i] = new int[capacity+];
for(int i=;i<goodsnum+;++i){
cin>>weight[i]>>value[i];
}
cout<<knapsack0N(goodsnum,capacity,weight,value,result,count)<<endl;
/*该循环用来计算每个物体装入的个数*/
for(int i=goodsnum;i>;){
if(result[i][capacity]==result[i-][capacity])//该条件下物体i不装入，count[i]不变，i--
i--;
else{
//该条件下物体i可以装入数目增加一个,i不变，在进入循环，看看i物体是否还能在装入
count[i]++;
capacity -= weight[i];
}
}
//将装入个数不为0的物体输出，并输出该物体装入的个数
for(int i=;i<goodsnum+;i++){
if(count[i]!=)
cout<<i<<" "<<count[i]<<endl;
}
return ; }