背包演算法c語言
『壹』 哪位大哥會寫「隨機背包演算法」c語言完整的程序呀，跪求!!!感激不盡！！！
13.Algorithm Gossip: 背包問題（Knapsack Problem）
說明假設有一個背包的負重最多可達8公斤，而希望在背包中裝入負重范圍內可得之總價物品，假設是水果好了，水果的空陸編號、單價與重量如下所示：
0 李子 4KG NT$4500
1 蘋果 5KG NT$5700
2 橘子 2KG NT$2250
3 草莓 1KG NT$1100
4 甜瓜 6KG NT$6700
解法背包問題是關於最佳化的問題，要解最佳化問題可以使用「動態規劃」（Dynamic programming），從空集合開始，每增加一個元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最後得到的就是最佳解。
以背包問題為例，我們使用兩個陣列value與item，value表示目前的最佳解所得之總價，item表示最後一個放至背包的水果，假設有負重量 1～8的背包8個，並對每個背包求其最佳解。
逐步將水果放入背包中，並求該階段的最佳解：
放入李子
背包負重 1 2 3 4 5 6 7 8
value 0 0 0 4500 4500 4500 4500 9000
item － － － 0 0 0 0 0
放入蘋果
背包負重 1 2 3 4 5 6 7 8
value 0 0 0 4500 5700 5700 5700 9000
item － － － 0 1 1 1 0
放入橘子
背包負重 1 2 3 4 5 6 7 8
value 0 2250 2250 4500 5700 6750 7950 9000
item － 2 2 0 1 2 2 0
放入草莓
背包負重 1 2 3 4 5 6 7 8
value 1100 2250 3350 4500 5700 6800 7950 9050
item 3 2 3 0 1 3 2 3
放入甜瓜
背包負重 1 2 3 4 5 6 7 8
value 1100 2250 3350 4500 5700 6800 7950 9050
item 3 2 3 0 1 3 2 3
由最後一個表格，可以得知在背包負重8公斤時，最多可以裝入9050元的水果，而最後一個裝入的 水果是3號，也就是草莓，裝入了草莓，背包只能再放入7公斤（8-1）的水果，所以必須看背包負重7公斤時的最佳解，最後一個放入的是2號，也滲漏就 是橘子，現在背包剩下負重量5公斤（7-2），所以看負重5公斤的最佳解，最後放入的是1號，也就是蘋果，此時背包負重量剩下0公斤（5-5），無法 再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為9050元。
實作
C
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 8 // 重量限制
#define N 5 // 物品種類
#define MIN 1 // 最小重叢虧爛量
struct body {
char name[20];
int size;
int price;
};
typedef struct body object;
int main(void) {
int item[LIMIT+1] = {0};
int value[LIMIT+1] = {0};
int newvalue, i, s, p;
object a[] = {{"李子", 4, 4500},
{"蘋果", 5, 5700},
{"橘子", 2, 2250},
{"草莓", 1, 1100},
{"甜瓜", 6, 6700}};
for(i = 0; i < N; i++) {
for(s = a[i].size; s <= LIMIT; s++) {
p = s - a[i].size;
newvalue = value[p] + a[i].price;
if(newvalue > value[s]) {// 找到階段最佳解
value[s] = newvalue;
item[s] = i;
}
}
}
printf("物品\t價格\n");
for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) {
printf("%s\t%d\n",
a[item[i]].name, a[item[i]].price);
}
printf("合計\t%d\n", value[LIMIT]);
return 0;
}
Java
class Fruit {
private String name;
private int size;
private int price;
public Fruit(String name, int size, int price) {
this.name = name;
this.size = size;
this.price = price;
}
public String getName() {
return name;
}
public int getPrice() {
return price;
}
public int getSize() {
return size;
}
}
public class Knapsack {
public static void main(String[] args) {
final int MAX = 8;
final int MIN = 1;
int[] item = new int[MAX+1];
int[] value = new int[MAX+1];
Fruit fruits[] = {
new Fruit("李子", 4, 4500),
new Fruit("蘋果", 5, 5700),
new Fruit("橘子", 2, 2250),
new Fruit("草莓", 1, 1100),
new Fruit("甜瓜", 6, 6700)};
for(int i = 0; i < fruits.length; i++) {
for(int s = fruits[i].getSize(); s <= MAX; s++) {
int p = s - fruits[i].getSize();
int newvalue = value[p] +
fruits[i].getPrice();
if(newvalue > value[s]) {// 找到階段最佳解
value[s] = newvalue;
item[s] = i;
}
}
}
System.out.println("物品\t價格");
for(int i = MAX;
i >= MIN;
i = i - fruits[item[i]].getSize()) {
System.out.println(fruits[item[i]].getName()+
"\t" + fruits[item[i]].getPrice());
}
System.out.println("合計\t" + value[MAX]);
}
}
『貳』 C語言背包問題遞歸演算法
你學過數據結構了嗎？如果學過，那就比較好理解，該演算法的思路和求二叉樹的高度的演算法的思路是十分類似的。把取這i個物體看成i個階段，則該二叉樹有i+1層。其中空背包時為根結點，左孩子則為放棄了第1個物品後的背包，右孩子為選取了第1個物品後的背包。今後在對第i個物品進行選擇時，向左表示放棄，向右表示選取。則遞歸演算法可如下：
int fun(int s, int i, int n) //s傳入的是背包容量, i是進行第i個物品的選取，n為剩餘物品的件數
{
if(s == 0) return 有解；
else if(剩餘的每件物品都裝不進|| n == 0) return 無解；
L = fun(s, i + 1, n - 1); //放棄第i個物品，則下一步的背包容量仍為s，然後看其是否有解，(遞歸調用進入左子樹)
R = fun(s - wi, i + 1, n - 1); //選取第i個物品，則下一步的背包容量為s-wi，然後看其是否有解，(遞歸調用進入右子樹)
return (l, r); //綜合考慮左右兩邊，看哪邊是正解或都無解。其實應該返回 return (L||R);
}
『叄』 求大神給一份C語言01背包的代碼，要每一行都有注釋，謝謝！
這是一個背包問題，該演算法已經是最簡單的了，還有遞歸演算法，我覺得更麻煩。對你的代碼進行解釋如下：
//背包問題：有m件物品和一個承重為t的背包。第i件物品的重量是w[i]，價值是v[i]。
//求解將哪些物品裝入背包可使這些物品的重量總和不超過背包承重量t，且價值總和最大。
#include<stdio.h>
#include<conio.h>
#include<string.h>
intf[1010],w[1010],v[1010];//f記錄不同承重量背包的總價值，w記錄不同物品的重量，v記錄不同物品的價值
intmax(intx,inty){//返回x,y的最大值
if(x>y)returnx;
粗消衡returny;
}
intmain(){
intt,m,i,j;
memset(f,0,sizeof(f));//總價值初始化為0
scanf("%d%d",&t,&m);橋純//輸入背包承重量t、物品的數目m
for(i=1;i<=m;i++)
scanf("%d%d",&w[i],&v[i]);//輸入m組物品的重量w[i]和價值v[i]
for(i=1;i<=m;i++){//嘗試放置每一個物品
for(j=t;j>=w[i];j--){
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i個物品前後，檢驗不同j承重量背包的總價值，如果放入第i個物品後比放入前的價值提高了，則岩做修改j承重量背包的價值，否則不變
}
}
printf("%d",f[t]);//輸出承重量為t的背包的總價值
printf(" ");
getch();
return0;
}
『肆』 c語言01背包問題誰能簡單說下
01背包問題就是有個容量為W的包，然後有一堆的物品(1...n)，其中wi、vi分別為第i個物品的重量和價值，現在需要求的就是使得包中所裝的物品盡可能的價值高。那麼這個物品放不放在包中對應取值0
or
1。其演算法為動態規劃，需要證明最優子結構性質。用s[i][j]表示只有前i個物品且包容量為j時所能等到的最大價值，而有遞歸式
s[i][j]=
s[i-1][j],
wi>j
max{s[i-1][j],s[i-1][j-wi]+vi},
wi<=j
s[0][j]=0
1<=j<=W
s[i][0]=0
1<=i<=n
所以不論用什麼語言實現，就是計算上面的式子，最終求得s[n][W]，上面的式子很好用遞推實現的，這個是自底向上的，就是兩層for；你也可以用棧實現自頂向下的，這個是記錄式的方法。
以上的W是只考慮整數的。
『伍』 c語言背包問題
演算法分析：
使用貪心策略求解此類問題時，首先要選出最優的度量標准。
可供選擇的度量標准有三種：價值，容量，單位價值（v/w，價值/重量）。
顯然，價值高的物品容量可能太大，容量大的物品價值也可能很低。最優的度量標準是單位價值。
背包困液問題演算法思路：
1、將各個物品按照單位價值由高到低排序；
2、取價值最高者放入背包；
3、計算背包的剩餘空間；
4、重復2-3步，直到背包剩餘容量=0或者物品全部裝入背包為止（對於0-1背包，終止條件為背包剩餘容量無法裝入任意一件物品或者物品全部裝入背包）。
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已經按照單位價值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被汪行物放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
if(i<=n)//還可以放入一個物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩餘容量為0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態帶團，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
}
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已經按照單位價值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
if(i<=n)//還可以放入一個物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩餘容量為0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
}
『陸』 編程序解決0 1 背包問題（c語言）
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace beibao
{
class np
{
private int c = 0;//容量
private wp[] w;//物品
private int cp = 0;//當前價值
private int cw = 0;//森納當前重量
private int bestp = 0;//當前最優值
///動態規劃中/////////////
private int[] head; //豎春旦輔助數組
private int[,] p; //輔助數組
public np(wp[] w,int c)
{
p = new int[9999, 2];
this.w = w;
this.c = c;
sort();
tanxin();
huisu();
dongtaiguihua();
}
public void sort()
{
wp wupin;
for (int i = 0; i < w.Length-1; i++)
{//從小到大冒泡排序
for (int j = 0; j < w.Length-i-1; j++)
{
if (w[i].danweizhongliang > w[i + 1].danweizhongliang)
{
wupin = w[i];
w[i] = w[i + 1];
w[i + 1] = wupin;
}
}
}
}
public void tanxin()
{
cp = cw = bestp = 0;
for (int i = 0; i < w.Length; i++)
{
w[i].State = false;
}
for (int i = 0; i < w.Length; i++)
{
if (cw + w[i].Weight > c)
continue;
cw += w[i].Weight;
cp += w[i].Price;
w[i].State = true;
}
Console.WriteLine("貪心演算法:裝入價值余擾"+cp.ToString());
Console.WriteLine("裝入物品號碼:");
for (int i = 0; i < w.Length; i++)
{
if (w[i].State == true) Console.Write(w[i].number.ToString() + "\t");
} Console.WriteLine();
}
public void huisu()
{
cp = cw = bestp = 0;
for (int i = 0; i < w.Length; i++)
{
w[i].State = false;
}
Backtrack(0);
Console.WriteLine("回溯法:裝入價值" + bestp.ToString());
Console.WriteLine("裝入物品號碼:");
for (int i = 0; i < w.Length; i++)
{
if (w[i].State == true) Console.Write(w[i].number.ToString() + "\t");
} Console.WriteLine();
}
private void Backtrack(int i)
{
if (i >= w.Length)
{
bestp = cp; return;
}
if (cw + w[i].Weight <= c)
{
cw += w[i].Weight;
cp += w[i].Price;
w[i].State = true;
Backtrack(i + 1);
cw -= w[i].Weight;
cp -= w[i].Price;
}
if (Bound(i + 1) > bestp)
{
Backtrack(i + 1); w[i].State = false;
}
}
private double Bound(int i)
{
int cleft = c - cw;
double b =(double ) cp;
while (i < w.Length && w[i].Weight <= cleft)
{
cleft -= w[i].Weight;
b += w[i].Price;
i++;
}
if (i < w.Length)
{
b += (double)w[i].Price * (double)cleft / (double)w[i].Weight;
}
return b;
}
public void dongtaiguihua()
{
cp = cw = bestp = 0;
for (int i = 0; i < w.Length; i++)
{
w[i].State = false;
}
int m= Knapsack(w.Length);
Console.WriteLine("動態規劃:裝入價值" + m.ToString());
Console.WriteLine("裝入物品號碼:");
for (int i = 0; i < w.Length; i++)
{
if (w[i].State == true) Console.Write(w[i].number.ToString() + "\t");
} Console.WriteLine();
}
private int Knapsack(int n)
{
head = new int[n + 2];
head[n + 1] = 0;
p[0, 0] = 0;
p[0, 1] = 0;
int left = 0;
int right = 0;
int next = 1;
head[n] = 1;
for (int i =n-1; i >= 0; i--)
{
int k = left;
for (int j = left; j <= right; j++)
{
if (p[j, 0] + w[i].Weight > c)
break;
int y = p[j, 0] + w[i].Weight;
int m = p[j, 1] + w[i].Price;
while (k <= right && p[k, 0] < y)
{
p[next, 0] = p[k, 0];
p[next++, 1] = p[k++, 1];
}
if (k <= right && p[k, 0] == y)
{
if (m < p[k, 1]) m = p[k, 1];
k++;
}
if (m > p[next - 1, 1])
{
p[next, 0] = y;
p[next++, 1] = m;
}
while (k <= right && p[k, 1] <= p[next - 1, 1])
k++;
}
while (k <= right)
{
p[next, 0] = p[k, 0];
p[next++, 1] = p[k++, 1];
}
left = right + 1;
right = next - 1;
head[i] = next;
}
Traceback(n);
return p[next - 1, 1];
}
private void Traceback(int n)
{
int j = p[head[0] - 1, 0];
int m = p[head[0] - 1, 1];
for (int i = 0; i < n; i++)
{
w[i].State = false;
for (int k = head[i + 1]; k <= head[i] - 1; k++)
{
if (p[k, 0] + w[i].Weight == j && p[k, 1] + w[i].Price == m)
{
w[i].State = true;
j = p[k, 0];
m = p[k, 1];
break;
}
}
}
}
}
/// <summary>
/// 物品類
/// </summary>
class wp
{
private int w = 0;
private int p = 0;
private int num;
private bool state=false;
public wp(int w,int p,int n)
{
this.w = w;
this.p = p;
num = n;
}
public int Weight
{
get
{
return w;
}
}
public int Price
{
get
{
return p;
}
}
public bool State
{
set
{
state = value;
}
get
{
return state;
}
}
public double danweizhongliang
{
get
{
return (double)p / (double)w;
}
}
public int number
{
get
{
return num;
}
}
}
}
//////////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace beibao
{
class Program
{
static void Main(string[] args)
{
np beobap;
int n = 0;
Console.WriteLine("物品數量");
n = Convert.ToInt32(Console.ReadLine());
wp[] wupin = new wp[n];
int c = 0;
Console.WriteLine("背包容積");
c = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < n; i++)
{//初始化
int w = 0; int p = 0;
Console.WriteLine("物品" + (i + 1) + "的重量");
w = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("物品" + (i + 1) + "的價值");
p = Convert.ToInt32(Console.ReadLine());
wupin[i] = new wp(w, p, i);
}
beobap = new np(wupin, c);
}
}
}
這是當初我上學的時候做的，應該沒什麼問題，你看看還可以修改修改，有什麼問題可以再問我
『柒』 C語言 背包問題 遞歸演算法
if(n==0)應該改成
if(n<0)才對，表示沒有物品可選了。我的一個改進，但輸出選擇項還是有問題！
#include<stdio.h>
#include<conio.h>
#defineN3
intMaxW(intn,intC,int*Volume,int*Weight,int*Select){
intW=0,W1=0;
if(n<0){//沒有物品了
return0;
}
W=MaxW(n-1,C,Volume,Weight,Select);//沒放入n之前的重量
if(C>=Volume[n]){//背包剩餘空間可以放下物品n
W1=MaxW(n-1,C-Volume[n],Volume,Weight,Select)+Weight[n];//放入n所能得到的重量
Select[n]=0;
if(W1>W){//放入n能獲得更大的重量
Select[n]=1;
W=W1;
}
}
returnW;
}
intmain(){
intC=8,W,i;
//intVolume[N]={1,2,3,4,5};//物品體積
//intWeight[N]={1,2,5,7,8};//物品重量
intVolume[N]={2,3,5};//物品體積
intWeight[N]={5,8,7};//物品重量
intSelect[N]={0};//選擇標記
W=MaxW(N-1,C,Volume,Weight,Select);
printf("MaxWeight=%d,SelectList[index(volume,weight)]: ",W);
for(i=0;i<N;++i){
if(Select[i]){
printf("%d(%d,%d)",i,Volume[i],Weight[i]);
}
}
printf(" Finished! ");
getch();
return0;
}
其中的Select數組還是會多選了，你看看。
『捌』 背包問題(C語言)
我一下別人的遞歸演算法，假如你有時間限時的話，那我就用動態規劃幫你重新code一個
#include <stdio.h>
#define N 100 //物品總種數不是常量，沒法根據它來決定數組的長度，只有先定義個長度了
int n;//物品總種數
double limitW;//限制的總重量
double totV;//全部物品的總價值
double maxv;//解的總價值
int option[N];//解的選擇
int cop[N];//當前解的選擇
struct {//物品結構
double weight;
double value;
}a[N];
//參數為物品i,當前選擇已經達到的重量和tw,本方案可能達到的總價值
void find(int i,double tw,double tv)
{
int k;
//物品i包含在當前方案的可能性
if(tw+a[i].weight <= limitW){
cop[i]=1;
if(i<n-1)find(i+1,tw+a[i].weight,tv);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在當前方案的可能性
if(tv-a[i].value>maxv){
if(i<n-1)find(i+1,tw,tv-a[i].value);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
void main()
{
int k;
double w,v;
printf("輸入物品種數:");
scanf("%d",&n);
printf("輸入各物品的重量和價值:");
for(totV=0.0,k=0;k<n;++k){
scanf("%lf %lf",&w,&v);
a[k].weight = w;a[k].value = v;
totV += v;
}
printf("輸入限制重量:");
scanf("%lf",&limitW);
maxv=0.0;
for(k=0;k<n;++k)cop[k]=0;
find(0,0.0,totV);
for(k=0;k<n;++k)
if(option[k])printf("%4d",k+1);
printf("總價值為: %2f",maxv);
}
『玖』 背包問題C語言簡短代碼，大神們最好帶解釋和注釋，謝謝！！！
不知道你說的哪種類型的背包，我就說下最簡單的吧。
一、01背包
問題描述：有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
（1）基本思路：這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則御悉仔其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
意思簡要來說就是：如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為鎮汪「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
（2）優化空間復雜度：以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i-1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符。
（3）初始化的細節問題：我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
【寫的偽代碼，能看懂哈。。。不懂再問好了】陸亮
『拾』 C語言那個背包問題的演算法。要口述。不要復制的。
就余碼是用二維狀態F[i][j]表示當前的最大價值，i為第幾個東西，j為背包大小，對於第i個物品有價值v[i]j，和大小s[i]，那麼轉移方程為f[i][n] = max(f[i-1][n-s[i]] + v[i],f[i][n]) 如果是物品只有一個春扮對於每個i你就從背包大小n for到0就可以了，這里需要保證n-s[i] >= 0。如果是物品無窮多那麼從0for到n就可以了。豎森哪。
純手打。。