微网站模板在线制作,便宜网站设计,大数据平台的整体搭建思路,免备案空间什么意思宣传一下算法提高课整理 —
CSDN个人主页#xff1a;更好的阅读体验 — 本题链接#xff08;AcWing#xff09; 点这里
题目描述
有 N N N 件物品和一个容量是 V V V 的背包。每件物品只能使用一次。
第 i i i 件物品的体积是 v i v_i vi#xff0c;价值…宣传一下算法提高课整理 —
CSDN个人主页更好的阅读体验 — 本题链接AcWing 点这里
题目描述
有 N N N 件物品和一个容量是 V V V 的背包。每件物品只能使用一次。
第 i i i 件物品的体积是 v i v_i vi价值是 w i w_i wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。
输出 字典序最小的方案。这里的字典序是指所选物品的编号所构成的序列。物品的编号范围是 1 … N 1 … N 1…N。
输入格式
第一行两个整数 N V NV NV用空格隔开分别表示物品数量和背包容积。
接下来有 N N N 行每行两个整数 v i , w i v_i, w_i vi,wi用空格隔开分别表示第 i i i 件物品的体积和价值。
输出格式
输出一行包含若干个用空格隔开的整数表示最优解中所选物品的编号序列且该编号序列的字典序最小。
物品编号范围是 1 … N 1 … N 1…N。
数据范围 0 N , V ≤ 1000 0 \lt N, V \le 1000 0N,V≤1000 0 v i , w i ≤ 1000 0\lt v_i, w_i \le 1000 0vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6输出样例
1 4思路
本题为DP问题可以使用 闫氏DP分析法 解题。
因为题目要求输出选法所以我们需要倒推状态转移路径而要求字典序最小我们需要在选和不选之间优先选当前物品。
所以我们把原本正序遍历的物品倒过来枚举这样我们选择的时候优先考虑选择该物品就可以了。
DP
状态表示 f i , j f_{i,j} fi,j 集合在后 i i i 个物品中选且总体积不超过 j j j 的所有方案。属性 max \max max 状态计算 选倒数第 i i i 个物品 f i 1 , j − v i w i f_{i1,j-v_i}w_i fi1,j−viwi不选倒数第 i i i 个物品 f i 1 , j f_{i1,j} fi1,j
时间复杂度 O ( N ⋅ V ) O(N \cdot V) O(N⋅V) AC Code: C C C #include iostreamusing namespace std;const int N 1010;int n, m;
int f[N][N];
int v[N], w[N];int main()
{scanf(%d%d, n, m);for (int i 1; i n; i )scanf(%d%d, v[i], w[i]);for (int i n; i 1; i -- )for (int j 1; j m; j ){f[i][j] f[i 1][j];if (j v[i])f[i][j] max(f[i][j], f[i 1][j - v[i]] w[i]);}int k m;for (int i 1; i n; i )if (k v[i] f[i][k] f[i 1][k - v[i]] w[i]){cout i ;k - v[i];}return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
