背包問題貪心演算法
A. C語言 貪心演算法求背包問題
是你的冒泡排序出了問題~
你吧 原來的1-2-3號按照東西的價值重新排列現在的1-2-3對應原來的2-1-3了
所以 你輸出的時候是按 1-2-3輸出的話 就等於第一個是原來的X2 第二個是X1第三個是X3
而且你的冒泡排序用錯了 只比較了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去學校幫你重新改改 我家的機器沒有C++
周一晚上我會上傳答案~我最近正好也要做演算法的作業~
#include <stdio.h>
#include <math.h>
#define N 50
float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放單位價值量大的物體，再考慮小的物體*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入數量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}
int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(
B. 貪心演算法中的背包問題求解答。C++代碼
按照性價比貪心是不對的，背包問題必須用動態規劃演算法。貪心有反例的
C. 背包問題的貪心演算法C＋＋
為啥不用動態規劃呢？
背包的貪心法是每次都選擇收益最大，如果包還能容納，就放入包裡面，並把這個物品去掉。
D. 求背包問題貪心演算法實例結果
找零錢問題：以人民幣1元，2元，5元，10元，20元，50元，100元為例，要求所找的張數最少
背包問題：假設物體重量W1，W2．．．Wn其對應的價值為P1，P2．．．Pn，物體可分割，求裝入重量限制為m的背包中的物體價值最大．可用P/W來解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的結構體
{
double p;//價值
double w;//重量
double r;//價值與重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品個數
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//調用sort排序函數，你大概不介意吧，按照價值與重量比排序貪心
scanf("%lf",&m);//讀入包的容量m
s=0;//包內現存貨品的重量
value=0;//包內現存貨品總價值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//輸出結果
return 0;
}
E. 用貪心演算法解決背包問題
用貪心演算法解決背包問題，首先要明白，結果不一定是全局最優的。對於貪心法而言，首先步驟是找到最優度量標准，我這里的演算法採用的最優度量標準是： 收益p/重量w 的值最大者優先放入背包中，所以有演算法如下：void GreedyKnapsack(float * x){ //前置條件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u為背包剩餘載重量，初始時為m for(int i=0;i<n;i++) x[i]=0; //對解向量x初始化 for(i=0;i<n;i++){ //按最優度量標准選擇的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}
F. 動態規劃背包問題與貪心演算法哪個更優
首先這兩個演算法是用來分別解決不同類型的背包問題的，不存在哪個更優的問題。
當一件背包物品可以分割的時候，使用貪心演算法，按物品的單位體積的價值排序，從大到小取即可。
當一件背包物品不可分割的時候，（因為不可分割，所以就算按物品的單位體積的價值大的先取也不一定是最優解）此時使用貪心是不對的，應使用動態規劃。
G. 貪心演算法 部分背包問題
[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。 ?
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量價值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
H. 急，分全拿出來了，演算法中的背包問題的貪心演算法
#include <stdio.h>
#include <iostream.h>
#define MAXWEIGHT 20
#define n 3
float pw[n]={0},x[n]={0};
int w[n]={0},p[n]={0};
void sort(int p[],int w[])
{
int temp1,temp2;
float temp;
int i,j;
for(i=0;i<n;i++)
{
pw[i]=float(p[i])/w[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pw[i]<pw[j])
{
temp=pw[i],pw[i]=pw[j],pw[j]=temp;
temp1=p[i],temp2=w[i];
p[i]=p[j],w[i]=w[j];
p[j]=temp1,w[j]=temp2;
}
}
}
}
void GreedyKnapsack(int p[],int w[])
{
int m=MAXWEIGHT,i;
for(i=0;i<n;i++) x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m) break;
x[i]=1.0;
m=m-w[i];
}
if(i<n) x[i]=float(m)/w[i];
}
void main()
{
int i;
printf("請輸入每個物體的效益和重量:\n");
for(i=0;i<n;i++)
{
cin>>p[i]>>w[i];
}
for(i=0;i<n;i++)
{
printf("原物體%d的效益和重量分別為%d,%d:\n",i+1,p[i],w[i]);
}
sort(p,w);
printf("\n\n\n按效益值非遞增順序排列物體:\n");
for(i=0;i<n;i++)
{
printf("物體%d的效益和重量分別為%d,%d 效益值為:%f\n",(i+1),p[i],w[i],pw[i]);
}
GreedyKnapsack(p,w);
printf("\n\n\n最優解為:\n");
for(i=0;i<n;i++)
{
printf("第%d個物體要放%f:\n",i+1,x[i]);
}
}
這是正確的演算法
I. 用貪心演算法能求解背包問題嗎為什麼,理由是什麼
一般的貪心策略都會造成解的丟失,動態規劃則是相當於枚舉了所有的解.
如果你有一個很好的貪心策略,背包問題也能用貪心策略來解決.但是,你是很難找到一個很好的貪心策略的.
J. 關於一道C語言的背包問題，用的是貪心演算法
//輸入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("請輸入第%d號物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必須大於0!\n");}
printf("請輸入第%d號物品的價值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的價值必須大於0!\n");}
bag[i].weight_t=bag[i].weight;
}
}
這部分中的
scanf("%f",&bag[i].benefit); //缺少&
把這行加上&就對了