设有n种物品，每种物品有一个重量及一个价值。
但每种物品的数量是无限的，
同时有一个背包，最大载重量为xk
今从n中物品中选取若干件
同一物品可以多次选取
使其重量的和小于等于xk
而价值的和最大
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
const int maxxk=401,maxn=21;
int w[maxn],u[maxn],get[maxn],f[maxn][maxxk];
int n,xk;
void init()
{
memset(w,0,sizeof(w));
memset(u,0,sizeof(u));
cin>>n>>xk;
for(int i=1;i<=n;i++) cin>>w[i]>>u[i];
}
void make()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<w[i];j++)
f[i][j]=______(1)______;
for(int j=w[i];j<=xk;j++)
if(f[i-1][j]>f[i][j-w[i]]+u[i])
_____(2)______;
else
_____(3)_______;
}
}
void print()
{
int i=____(4)____,j=______(5)_____;
while(i>0)
{
if(f[i][j]==f[i-1][j])
i--;
else
{
j-=w[i];
get[i]=_____(6)______;
}
}
cout<<"n="<<n<<","<<"xk="<<xk<<endl;
cout<<"max worth="<<_____(7)______<<endl;
for(int i=1;i<=n;i++)
cout<<"no."<<i<<",weight:"<<setw(2)<<w[i]<<",worth:"<<setw(2)<<u[i]<<",get"<<setw(2)<<get[i]<<endl;
}
int main()
{
init();
make();
print();
return 0;
}