【问题描述】
有1个容量为m的背包，现有n种物品，重量分别为w1,w2…wn，价值分别为v1,v….vn,若每种物品有无限多件，求能放入的最大总价值。
【输入格式】
第一行：两个整数m(m<=200)和n(n<=30)
第2~n+1，每行两个整数wi和vi
【输出格式】
一个数据，最大总价值
【输入样例】
10 4
2 1
3 3
4 8
7 9
【输出样例】
max=17
本题用背包算法即可求解，值得一提的是本题的边界问题需要好好考虑。
背包问题的解析如下：https://www.jianshu.com/p/f3f632df6649
代码如下：
#include<iostream>
#define max(x,y) (x)>(y)?(x):(y)
using namespace std;
fun(int n,int *w,int *v,int c){
int dp[n+1][c+1];
//边界初始化
for(int i=0;i<=c;i++){
dp[0][i]=0;
}
//！！！注意左边上也要
for(int i=0;i<=n;i++){
dp[i][0]=0;
}
//这里我分了三种情况讨论
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
if(j>w[i]){
dp[i][j]=max(dp[i][j-w[i]]+v[i],dp[i-1][j]);
}
else if(j==w[i])
dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
else
dp[i][j]=dp[i-1][j];
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=c;j++)
cout<<dp[i][j]<<" ";
cout<<'\n';
}
cout<<'\n';
cout<<"背包内最大价值为"<<dp[n][c];
delete []dp;
}
int main(){
int c;
cout<<"请输入背包容量c"<<endl;
cin>>c;
int n;
cout<<"请输入n"<<endl;
cin>>n;
int w[n+1];
int v[n+1];
cout<<"请输入物品重量,物品价值"<<endl;
for(int i=1;i<=n;i++){
cin>>w[i];
cin>>v[i];
}
fun(n,w,v,c);
} 