题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
样例
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
算法1
暴力递归
时间复杂度 太大（过了4个数据）
C++ 代码
#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],s[N];
int V,n;
//决策第k个物品，剩余空间为restV，的最大价值;
int f(int v[],int w[],int s[],int k,int restV,int n){
if(restV<=0||k>n){ //如果已经拿完最后一件物品，或者剩余空间小于等于0，则返回价值0；
return 0;
}
int values=0;
for(int i=0;i*v[k]<=restV&&i<=s[k];i++){ //拿i件第k个物品
values=max(values,f(v,w,s,k+1,restV-i*v[k],n)+i*w[k]);
}
return values;
}
int main(){
cin>>n>>V;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
cout<<f(v,w,s,1,V,n)<<endl;
return 0;
}
算法2
暴力枚举改动态规划（有重复计算过程，暴力递归自然过渡到动态规划）
时间复杂度
C++ 代码
#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],s[N];
int dp[N][N]; //dp[i][j]：决策第i件物品且剩余空间为j时，所能获得的最大价值
int V,n;
int main(){
cin>>n>>V;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=0;i<=V;i++){ //先初始化dp表的最后一行
if(i/v[n]<=s[n]) //第n件物品的数量不超过已有数量时
dp[n][i]=w[n]*(i/v[n]);
else //若超过，则即使剩余空间i增加，最大值dp[n][i]也不在增加
dp[n][i]=dp[n][i-1];
}
for(int i=n-1;i>0;i--){ //从倒数第二行行开始向上填写dp表
for(int j=0;j<=V;j++){ //列方向从左向右填
int values=0;
for(int k=0;k<=s[i]&&k*v[i]<=j;k++) //模仿暴力递归，拿k件第i个物品
values=max(values,dp[i+1][j-(k*v[i])]+w[i]*k);
dp[i][j]=values;
}
}
cout<<dp[1][V]<<endl;
return 0;
}
算法3
动态规划之压缩空间 （还可以再压）
朴素观察，二维dp数组可以压为俩行的滚动二维数组
时间复杂度 同上
C++ 代码
#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],s[N];
//int dp[N][N]; //dp[i][j]：决策第i件物品且剩余空间为j时，所能获得的最大价值
int dp[2][N]; //压缩空间：dp[k][j]: 决策第i件物品且剩余空间为j时，所能获得的最大价值，其中k=i%2;
int V,n;
int main(){
cin>>n>>V;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=0;i<=V;i++){ //先初始化dp表的最后一行
if(i/v[n]<=s[n]) //第n件物品的数量不超过已有数量时
dp[n%2][i]=w[n]*(i/v[n]);
else //若超过，则即使剩余空间i增加，最大值dp[n][i]也不在增加
dp[n%2][i]=dp[n%2][i-1];
}
for(int i=n-1;i>0;i--){ //从倒数第二行行开始向上填写dp表
for(int j=0;j<=V;j++){ //列方向从左向右填
int values=0;
for(int k=0;k<=s[i]&&k*v[i]<=j;k++) //模仿暴力递归，拿k件第i个物品
values=max(values,dp[(i+1)%2][j-(k*v[i])]+w[i]*k);
dp[i%2][j]=values;
}
}
cout<<dp[1][V]<<endl;
return 0;
}
算法4 （以下为参考题解内容，技巧挺多）
动态规划之压缩空间（最省，当然还可以压缩输入数据空间，暂不考虑）
时间复杂度 同上
参考文献 参考题解
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int w[MAXN]; // 重量
int v[MAXN]; // 价值
int s[MAXN]; // 物品数量
int f[MAXN]; // f[i][j], j重量下前i个物品的最大价值
int main()
{
int n;
int m; // 背包重量
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> w[i] >> v[i] >> s[i];
for(int i = 1; i <= n; ++i)
for(int j = m; j>=0; --j)
for(int k = 1; k <= s[i]; ++k)
if(j>=k*w[i])
f[j] = max(f[j], f[j-k*w[i]]+k*v[i]);
cout << f[m] << endl;
return 0;
}
算法5
改为0-1背包
时间复杂度 同上
参考文献 参考题解
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+100;
ll v[N],w[N];
ll f[N];
int main()
{
ll n,m;
ll cnt=1;
cin>>n>>m;
ll a,b,c;
for(ll i=1;i<=n;i++)
{
cin>>a>>b>>c;
for(ll j=1;j<=c;j++)
{
v[cnt]=a;
w[cnt]=b;
cnt++;
}//将多重背包一个一个拆出来
}
for(ll i=1;i<=cnt;i++)
{
for(ll j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}//01背包
cout<<f[m];
return 0;
}
