【板子】 0-1背包问题 一维数组

0-1背包问题

有 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

输出样例：

8

实现代码

#include<bits/stdc++.h> using namespace std;const int maxn=1010; int v[maxn],w[maxn]; int dp[maxn];int main() {int m,n;scanf("%d %d",&m,&n);for(int i=1;i<=m;i++){scanf("%d %d",&v[i],&w[i]);}for(int i=1;i<=m;i++){for(int j=n;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//动态规划 }}printf("%d",dp[n]);//表示当前容量能达到的最大价值 return 0; }

总结

以上是生活随笔为你收集整理的【板子】 0-1背包问题 一维数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。