题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示:
本题考查多重背包的二进制优化方法。
样例
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
算法1
(动态规划)
首先来看看题目给的数据范围:: 0~2000,很好如果直接暴力,不用说肯定-TLE- bomb
核心操作就是“分”
如下所示:
int k=1;
while(k<=c)
{
cnt++;
val[cnt]=k*b;
we[cnt]=k*a;
c-=k;
k<<=1;
}
if(c>0)
{
cnt++;
val[cnt]=c*b;
we[cnt]=c*a;
}
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000;
int dp[N << 1],we[N << 1],val[N << 1],n,m,k,cnt;
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()
{
cnt=0;
n = read(); //种类
m = read(); //背包体积
for(int i=1;i<=n;i++)
{
int a,b,c;
//a - 该物品的体积
//b - 该物品的价值
//c - 该物品的数量
a = read();
b = read();
c = read();
int k=1;
while(k<=c) //大数化小,小数化了,采用“二”进制,来逐步分解 c ;
{
cnt++;//下标
val[cnt]=k*b; //每次得到的 k ,来更新val[cnt];
we[cnt]=k*a; //同上。
c-=k;
k<<=1; // "<<"位移符合,相当于 乘于二;
}
if(c>0)
{
cnt++;
val[cnt]=c*b;
we[cnt]=c*a;
}
}
n=cnt;//千万别忘了!
for(int i=1;i<=n;i++)
{
for(int j=m;j>=we[i];j--)
{
dp[j]=max(dp[j],dp[j-we[i]]+val[i]); //转移方程
}
}
printf("%d",dp[m]);输出
return 0;
}