背包1
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
有n个重量和价值分别为Wi,Vi的物品,现从这些物品中挑选出总量不超过 W 的物品,求所有方案中价值总和的最大值。
Output:
输出为一行,即所有方案中价值总和的最大值。
Sample Input:
3 4
1 2
2 5
3 7
Sample Output:
9
解题思路:简单的01背包,一维滚动数组实现,空间优化到O(W),时间复杂度仍为O(nW)。通过二维数组的计算过程中可以发现:第i件物品放与不放的结果dp[i,j]只与上一个状态的计算结果dp[i-1,j]和dp[i-1,j-wi]有关,而前面储存的信息dp[0~i-2,jor(j-wi)]再也没有用到了,那就将其舍弃,换用一维数组dp[j]来代表dp[i,j]。由二维数组状态转移方程dp[i,j]=max(dp[i-1,j],dp[i-1,j-wi]+vi)可得一维数组状态转移方程dp[j]=max(dp[j],dp[j-wi]+vi)。注意:第二重循环要逆序枚举W~w[i],这样才保证了每件物品只被拿一次,即保证了计算dp[j]时dp[j-wi]保存的是上一个状态dp[i-1,j-wi]的值,而不是当前状态dp[i][j-wi]的值,这个不难证明可以手动模拟一下。
AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=10005;
4 int n,W,v[maxn],w[maxn],dp[maxn];//dp数组始终记录当前体积的最大价值
5 int main(){
6 while(cin>>n>>W){
7 for(int i=0;i<n;i++)
8 cin>>w[i]>>v[i];
9 memset(dp,0,sizeof(dp));
10 for(int i=0;i<n;++i) //个数
11 for(int j=W;j>=w[i];--j) //01背包
12 dp[j]=max(dp[j],dp[j-w[i]]+v[i]); //比较放入i物体后的价值与不放之前的价值,记录大的值
13 cout<<dp[W]<<endl;//输出总体积的最大值
14 }
15 return 0;
16 }