哔哩哔哩网站——动态规划基础背包问题(1) 01背包

视频网址——哔哩哔哩网站——动态规划基础背包问题(1) 01背包

滚动数组

背包问题——优化算法——阶梯跳跃点

// #include "everything.h"
#include <bits/stdc++.h> // 错误代码
using namespace std;
int N, V, dp[1001][100001], c[100001], w[100001]; // c重量、w价值
int main()
{
    int i, j;
    cin >> N >> V;
    for (i = 1; i <= N; i++)
        cin >> c[i] >> w[i]; // 读入每个物品的重量与收益
    for (i = 1; i <= N; i++)
    {
        for (j = V; j >= 0; j--)
        {
            if (j < c[i])
                break;
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;
    system("pause");
    return 0;
}

哔哩哔哩网站——【动态规划】背包问题

视频网址——哔哩哔哩网站——【动态规划】背包问题

回溯：没有与10相同的，所以物品4一定被装入背包了。背包空间为8，物体4体积为5，背包中剩余的空间“3”用来装其它物品。考虑背包容量为3的时候，最佳物品组合。—> 考虑3号物品到底有没有被装入背包 —> 若3号物品未被装入背包，考虑前两个物品装入背包的情况即可。

Java代码实现：https://www.cnblogs.com/jiyongjia/p/13475026.html

代码——原文链接

package Z;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Beibao {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new LinkedHashMap<>();
        map.put(2, 3);
        map.put(3, 4);
        map.put(4, 5);
        map.put(5, 6);
        System.out.print("背包可容纳最大价值：" + getMaxValue(map, 8));
    }
    private static Integer getMaxValue(Map<Integer, Integer> gems, int capacity) {
        int[][] maxValue = new int[gems.size() + 1][capacity + 1];
        List<Integer> gemList = new ArrayList<>();
        int choose, notChoose;
        for (int i = 0; i < gems.size() + 1; i++) {
            maxValue[i][0] = 0;
        }
        for (int i = 0; i < capacity + 1; i++) {
            maxValue[0][i] = 0;
        }
        gemList.add(0);
        for (Integer gemKey : gems.keySet()) {
            gemList.add(gemKey);
        }
        for (int i = 1; i < gems.size() + 1; i++) {
            for (int j = 1; j < capacity + 1; j++) {
                if (gemList.get(i) > j) {
                    maxValue[i][j] = maxValue[i - 1][j];
                } else {
                    choose = gems.get(gemList.get(i)) + maxValue[i - 1][j - gemList.get(i)];
                    notChoose = maxValue[i - 1][j];
                    maxValue[i][j] = Math.max(choose, notChoose);
                }
            }
        }
        for (int i = 0; i < gems.size() + 1; i++) {
            for (int j = 0; j < capacity + 1; j++) {
                System.out.print(maxValue[i][j] + " ");
            }
            System.out.println();
        }
        getDetails(maxValue, gems, gemList, gems.size() + 1, capacity + 1);
        return maxValue[gems.size()][capacity];
    }
    private static void getDetails(int[][] maxValue, Map<Integer, Integer> gems, 
            List<Integer> gemList, int rows, int cols) {
        List<Integer> details = new ArrayList<>();
        while (rows > 1 && cols > 1) {
            if (maxValue[rows - 1][cols - 1] != maxValue[rows - 2][cols - 1]) {
                details.add(rows - 1);
                rows--;
                cols = cols - 1 - gemList.get(rows - 1);
            } else {
                rows--;
            }
        }
        System.out.println("装入背包的有：");
        for (int i = 0; i < details.size(); i++) {
            System.out.println(
                    "体积为" + gemList.get(details.get(i)) + ",价值为" + gems.get(gemList.get(details.get(i))) + "的石头");
        }
    }
}