动态规划--背包问题

以你之姓@ 2023-02-15 12:58 49阅读 0赞

/* 问题描述： W的书包装，n件物品（依此w[i]、P[i]）如何选取使得利益最大 思路： 按P[i]/w[i]排序进行选择，直至不能选择 数据结构：类 */
    #include<iostream>
    #include<algorithm>
    using namespace std;
    class Knap { 
    	public:
    		Knap(int N,float M,float *weight,float *P);
    		void greedy(float *x);
    		float MaxPro(float *X);
    		// int ReturnOder();
    	private:
    		int n;
    		float m,*w,*p;
    		// int *order;
    };
    /*int Knap::ReturnOder(){ while() }*/
    
    float Knap::MaxPro(float *X) { 
    	float MaxProfile=0;
    	int i=0;
    	while(X[i]) { 
    		MaxProfile+=X[i]*p[i];
    		i++;
    	}
    	return 	MaxProfile;
    }
    Knap::Knap(int N,float M,float *weight,float *P) { 
    	n=N;
    	m=M;
    	w=weight;
    	p=P;
    }
    void Knap::greedy(float *x) { 
    	for(int i=0; i<n; i++)x[i]=0;
    	float u=m;
    	for(int i=0; i<n; i++) { 
    		if(w[i]<u) { 
    			x[i]=1;
    			u-=w[i];
    		} else { 
    			x[i]=u/w[i];
    			break;
    		}
    	}
    }
    
    int main() { 
    
    
    	int M=6,N=3,order[3]= { 0,1,2};
    	float WW[3]= { 2,3,4},PP[3]= { 1,2,4};
    
    	for(int i=0; i<N; i++) { 
    		for(int j=0; j<N-1-i; j++) { 
    			if(PP[j]/WW[j]<PP[j+1]/WW[j+1]) { 
    				swap(PP[j],PP[j+1]);
    				swap(WW[j],WW[j+1]);
    				swap(order[j],order[j+1]);
    			}
    		}
    	}
    	Knap KK(N,M,WW,PP);
    	float XX[3];
    	KK.greedy(XX);
    	cout<<"Max:"<<KK.MaxPro(XX);
    cout<<XX[0]<<" "<<XX[1]<<" "<<XX[2];
    
    	int i=0;
    	cout<<"序列：";
    while(XX[i]) { 
    		cout<<order[i]<<"->";
    		i++;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，49人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-背包问题

动态规划--背包问题

悠悠/ 2024年04月23日 20:02/ 0 赞/ 231 阅读

相关背包问题-动态规划

[背包问题九讲][Link 1] [背包问题参考博客][Link 2] 文章目录介绍: 背包问题 01背包问题

逃离我推掉我的手/ 2023年08月17日 17:42/ 0 赞/ 240 阅读

相关动态规划——背包问题

背包问题 -------------------- 目录 1. 概述 2. 背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个

叁歲伎倆/ 2023年06月30日 08:58/ 0 赞/ 186 阅读

相关动态规划--背包问题

/ 问题描述： W的书包装，n件物品（依此w[i]、P[i]）如何选取使得利益最大思路：按P[i]/w[i]排序进行选择，直至不能选择数据结构：类 / i

以你之姓@/ 2023年02月15日 12:58/ 0 赞/ 50 阅读

相关背包型动态规划——背包问题6

给出一个都是正整数的数组 `nums`，其中没有重复的数。从中找出所有的和为 `target` 的组合个数。示例：输入: nums = [1, 2, 4

阳光穿透心脏的1/2处/ 2022年10月27日 12:06/ 0 赞/ 295 阅读

相关背包型动态规划——背包问题3

给定 `n` 种物品, 每种物品都有无限个. 第 `i` 个物品的体积为 `A[i]`, 价值为 `V[i]`. 再给定一个容量为 `m` 的背包. 问可以装入背包的

傷城~/ 2022年10月27日 12:06/ 0 赞/ 314 阅读

相关背包型动态规划——背包问题1

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\] 示例：样例 1: 输入: [3,4,8,5]

旧城等待，/ 2022年10月27日 06:30/ 0 赞/ 302 阅读

相关背包型动态规划——背包问题2

有 `n` 个物品和一个大小为 `m` 的背包. 给定数组 `A` 表示每个物品的大小和数组 `V` 表示每个物品的价值. 问最多能装入背包的总价值是多大? 样例

忘是亡心i/ 2022年10月27日 06:29/ 0 赞/ 290 阅读

相关背包问题，动态规划

将下面四个重量的物品1，2，2，3 价值分别是9，3，3，6 装进重量为4的背包中，使得背包的重量不超过4，并且价值最大。 include<iostream>

左手的ㄟ右手/ 2022年02月28日 14:50/ 0 赞/ 444 阅读

相关动态规划背包问题

[本篇博文参考此博文，该博文PPT非常有助理解][PPT] > 问题描述： > 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背

傷城~/ 2021年09月11日 08:42/ 0 赞/ 582 阅读