动态规划之背包问题
2023-05-01 18:24:04 272浏览
动态规划之背包问题，现有一背包的容量为capacity现有一些物品，物品有重量和价值两个属性，物品的重量存在weight数组中，物品的价值存在value数组中，为了方便，其中没有负数。限制的条件是每个物品只有一种，要么放入背包，要么不放入，如何才能使得背包获得最大的价值，也就是在不超过背包容量的情况下背包能从物品中获得最大的价值，最终的结果，背包可以不被放满。
题目
现有一背包的容量为capacity
现有一些物品，物品有重量和价值两个属性，物品的重量存在weight数组中，物品的价值存在value数组中，为了方便，其中没有负数。
限制的条件是每个物品只有一种，要么放入背包，要么不放入，如何才能使得背包获得最大的价值，也就是在不超过背包容量的情况下背包能从物品中获得最大的价值，最终的结果，背包可以不被放满。
思路一：普通递归
两种选择，对于当前index下标的数组值，可以选择要和不要两种情况，比较两种情况下取获得价值大的。
public static int maxValueOne(int capacity, int[] weight, int[] value){
if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){
return 0;
}
return processOne(capacity, weight, value, 0);
}
/**
* @param rest 背包剩余重量
* @param weight 重量数组
* @param value 价值数组
* @param index 数组下标
* @return
*/
public static int processOne(int rest, int[] weight, int[] value, int index){
//当剩余重量小于0时，表示当前物品不能要，注意：有可能重量等于0还有价值的情况
//如果rest 为负数表示当前的index是不可用的，所以value[index]值就无效，返回 -1
if(rest < 0){
return -1;
}
if(index == weight.length){ //超过界限不取
return 0;
}
int next = processOne(rest - weight[index], weight, value, index +1);
int ans1 = 0;
if(next != -1){
//要当前物品
ans1 = value[index] + next;
}
//不要当前物品
int ans2 = processOne(rest, weight, value, index + 1);
//取最大值
return Math.max(ans1, ans2);
}思路二：傻缓存方式
分析有没有重复的过程，可以根据下标配合剩余背包容量进行确认值，假设背包容量为20，且当前index = 3，状态一是取0和2，不取1，此时剩余背包容量rest = 20 - 4 = 16，状态二是取1，不取2和3，此时剩余容量也是16，有重复过程。
public static int maxValueTwo(int capacity, int[] weight, int[] value){
if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){
return 0;
}
int N = weight.length;
int[][] dp = new int[N+1][capacity+1];
//初始化
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= capacity; j++) {
dp[i][j] = -1;
}
}
return processTwo(capacity, weight, value, 0, dp);
}
public static int processTwo(int rest, int[] weight, int[] value, int index, int[][] dp){
if(rest < 0){
return -1;
}
if(index == weight.length){
return 0;
}
if(dp[index][rest] != -1) {
return dp[index][rest];
}
int next = processTwo(rest - weight[index], weight, value, index+1, dp);
int ans1 = 0;
if(next != -1){
ans1 = value[index] + next;
}
int ans2 = processTwo(rest, weight, value, index+1, dp);
int max = Math.max(ans1, ans2);
dp[index][rest] = max;
return max;
}思路三：动态规划精髓-直接取值法
public static int maxValueThree(int capacity, int[] weight, int[] value){
if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){
return 0;
}
int N = weight.length;
int[][] dp = new int[N+1][capacity+1];
//直接赋值
for (int i = N-1; i >= 0; i--) {
for (int j = 0; j <= capacity; j++) {
//i位置的值取
int next = j - weight[i] < 0 ? -1 : dp[i+1][j-weight[i]];
int ans1 = 0;
if(next != -1){
ans1 = value[i] + next;
}
//i位置的值不取
int ans2 = dp[i+1][j];
//比较然后存值
dp[i][j] = Math.max(ans1, ans2);
}
}
return dp[0][capacity];
}总结测试
public class Knapsacks {
public static int maxValueOne(int capacity, int[] weight, int[] value){
if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){
return 0;
}
return processOne(capacity, weight, value, 0);
}
/**
* @param rest 背包剩余重量
* @param weight 重量数组
* @param value 价值数组
* @param index 数组下标
* @return
*/
public static int processOne(int rest, int[] weight, int[] value, int index){
//当剩余重量小于0时，表示当前物品不能要，注意：有可能重量等于0还有价值的情况
//如果rest 为负数表示当前的index是不可用的，所以value[index]值就无效，返回 -1
if(rest < 0){
return -1;
}
if(index == weight.length){ //超过界限不取
return 0;
}
int next = processOne(rest - weight[index], weight, value, index +1);
int ans1 = 0;
if(next != -1){
//要当前物品
ans1 = value[index] + next;
}
//不要当前物品
int ans2 = processOne(rest, weight, value, index + 1);
//取最大值
return Math.max(ans1, ans2);
}
public static int maxValueTwo(int capacity, int[] weight, int[] value){
if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){
return 0;
}
int N = weight.length;
int[][] dp = new int[N+1][capacity+1];
//初始化
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= capacity; j++) {
dp[i][j] = -1;
}
}
return processTwo(capacity, weight, value, 0, dp);
}
public static int processTwo(int rest, int[] weight, int[] value, int index, int[][] dp){
if(rest < 0){
return -1;
}
if(index == weight.length){
return 0;
}
if(dp[index][rest] != -1) {
return dp[index][rest];
}
int next = processTwo(rest - weight[index], weight, value, index+1, dp);
int ans1 = 0;
if(next != -1){
ans1 = value[index] + next;
}
int ans2 = processTwo(rest, weight, value, index+1, dp);
int max = Math.max(ans1, ans2);
dp[index][rest] = max;
return max;
}
public static int maxValueThree(int capacity, int[] weight, int[] value){
if(capacity < 0 || weight == null || value == null || weight.length == 0 || value.length == 0 || weight.length != value.length){
return 0;
}
int N = weight.length;
int[][] dp = new int[N+1][capacity+1];
//直接赋值
for (int i = N-1; i >= 0; i--) {
for (int j = 0; j <= capacity; j++) {
//i位置的值取
int next = j - weight[i] < 0 ? -1 : dp[i+1][j-weight[i]];
int ans1 = 0;
if(next != -1){
ans1 = value[i] + next;
}
//i位置的值不取
int ans2 = dp[i+1][j];
//比较然后存值
dp[i][j] = Math.max(ans1, ans2);
}
}
return dp[0][capacity];
}
//生成两个数组返回
public static int[][] generateArray(int maxSize, int maxValue){
int size = (int)((maxSize + 1) * Math.random());
int[][] arr = new int[2][size];
for (int i = 0; i < size; i++) {
arr[0][i] = (int)((maxValue + 1) * Math.random());
arr[1][i] = (int)((maxValue + 1) * Math.random());
}
return arr;
}
public static void main(String[] args) {
int testTime = 1000;
int maxSize = 100;
int maxValue = 100;
for (int i = 0; i < testTime; i++) {
int[][] array = generateArray(maxSize, maxValue);
int capacity = (int)(100*(Math.random()));
int one = maxValueOne(capacity, array[0], array[1]);
int two = maxValueTwo(capacity, array[0], array[1]);
int three = maxValueThree(capacity, array[0], array[1]);
if(one != two || one != three){
System.out.println("小伙子，有点问题，再改改！！！");
}
}
System.out.println("真不错，perfect！！！");
}
}好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
暂无评论，快来写一下吧
展开评论
您可能感兴趣的博客
