题目描述
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
样例
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
算法1
几乎与01背包的一维解答一模一样,唯一的区别是v的遍历次序是递增的。
那么就是说明dp转移方程
dp[j] = max(dp[j] , dp[j-v[i]]+w[i]);
dp依赖的状态未必是i-1轮的状态 而是同一轮中较小的j。 这也符合题意。
01背包中要验证当前第i个物品是否拿还是不拿必须依赖上一轮(i-1)轮的状态,这个状态是绝对不会出现已经拿取了第i个物品的情况。
但是在完全背包中,由于物品有多个,可能要验证当前是否拿第i个物品所依赖的状态已经取过若干个第i个物品了
所以v的遍历是由小到大递增的。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1010;
int n,m;
int arr[N];
int v[N];
int w[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> v[i] >> w[i];
}
for(int i = 1;i<=n;i++){
for(int j = v[i];j <= m ;j++){
arr[j] = max(arr[j] , arr[j-v[i]]+w[i]);
}
}
cout << arr[m];
return 0;
}
这个一维的思路 如果把j++换成 j=z*v[i] (z从1开始每次循环+1) 照理来说不应该更快吗 可是为什么我的答案出来是错的 是我的理解错了吗?
说个我的思路 ,不见的正确。
在此次的循环中 取走的体积肯定是v[i]
但是 j在此次选择的起点 还取决于之前的方案,所以尽可能是5的起点 也可能是4的起点也可能是3的起点。
所以必须j++ 而不是 j=z*v[i]