题解题解【动态规划】0/1背包问题
hymcr05
题目描述
有个背包可承受重量 N，现有 T 件物品
每件物品重量为 Wi,价值为 Vi ,每件物品只有一个,
这个背包可以装载物品的最大价值是多少?
输入
从文件 beibao1.in 中读入数据。
一行两个正整数 N T，之间用空格隔开
后面T行,每行两个正整数，分别表示重量 Wi,价值 Vi
输出
输出到文件 beibao1.out 中。
这个背包可以装载物品的最大价值
样例输入
1
2
3
4
5
6
| 100 5
77 92
22 22
29 87
50 46
99 90
|
样例输出
正片开始
这是一道十分不淼的题，致以本蒟蒻打下了大片江山：
额，这题就是塞更多的东西进有空间限制的背包嘛
首先想到了贪心，先排个序嘛，然后再拿价值大的物品，结果不行，别问为什么，你猜答案错误27.3是怎么来的？
正解即为：开一个 D P数组，下标表示这个 DP 数组最大可以存的数，然后一个个试物品，代码：（看不懂就算了）x 代表：容量/重量，y 表示价值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| if(dp[j].x==0 && dp[j].x+a[i].x<=j) {
dp[j].x+=a[i].x;
dp[j].y+=a[i].y;
continue;
}
if(dp[j].x!=0) {
if(dp[j].x+a[i].x<=j) {
dp[j].x+=a[i].x;
dp[j].y+=a[i].y;
int xx=j-dp[j].x;
dp[j].x+=dp[xx].x;
dp[j].y+=dp[xx].y;
} else {
if(dp[j].y<=a[i].y) {
dp[j].y=a[i].y;
dp[j].x=a[i].x;
}
}
}
|
优化一下》》
1
2
3
| for (int i=1; i<=t; i++)
for(int j=n; j>=a[i].x; j--)
dp[j]=max(dp[j-a[i].x]+a[i].y,dp[j]);
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
int n, t;
struct Node {
int x, y;
} a[99999999];
int dp[9999999];
int ans;
int main() {
cin>>n>>t;
for (int i=1; i<=t; i++) {
cin>>a[i].x>>a[i].y;
}
for (int i=1; i<=t; i++)
for(int j=n; j>=a[i].x; j--)
dp[j]=max(dp[j-a[i].x]+a[i].y,dp[j]);
cout<<dp[n];
return 0;
}
|
