背包算法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就可以了。竖森哪。
纯手打。。