题目描述
有 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
(暴力枚举) $O(n^2)$
看题目给的数据范围 小于100,so 我们可以暴力枚举一波!
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200;
int dp[N << 1],sum[N << 1],w[N << 1],v[N << 1],n,m,s;
int read() 快读
{
char c = getchar();
int f = 1, x = 0;
while(!isdigit(c)) {if(c == '-') f = -1;c = getchar();}
while(isdigit(c)){x = x * 10 + c - 48;c = getchar();}
return x * f;
}
int main()
{
n = read(); //种类
m = read(); //背包的体积
for(int i=1;i<=n;i++)
{
v[i] = read();//该物品的体积
w[i] = read();//该物品的价值
sum[i] = read();//该物品的数量
}
for(int i=1;i<=n;i++) //然后开始暴力枚举,直接三连循环
{
for(int j=m;j>=v[i];j--) //从大到小
{
for(int k=1;k<=sum[i];k++) //寻找合适的数量
{
if(j>=k*v[i]) //如果这些物品的总体积小于‘j’
{
dp[j]=max(dp[j],dp[j-v[i]*k]+k*w[i]); //就开始状态转移 ; 因为是 k 个物品,so 我们要乘 k 个;
}
}
}
}
printf("%d",dp[m]); //最后输出
return 0;
}
#include[HTML_REMOVED]
using namespace std;
const int N = 110 ;
int v[N], w[N] , s[N];
int f[N][N];
int n , m ;
int main()
{
cin >> n >> m ;
for(int i = 1 ; i <= n ; i) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i<= n ; i)
{
for(int j = m ; j >= v[i] ; j–)
{
for(int k = 1 ; k <= s[i] && k * v[i] <= j ; k++)
{
f[j] = max(f[j] , f[j-k*v[i]] + (k * w[i]));
}
}
}
cout << f[m] ;
return 0 ;
}
大佬,为啥我这样写max里面是(int【100】,int*)昂,右边为什么是指针?