背包问题（c/python)

假定背包的最大容量为W，N件物品，每件物品都有自己的价值和重量，将物品放入背包中使得背包内物品的总价值最大

假设有负重量 1～8的背包8个
构建N*W矩阵

行#0-4表示加入的物品编号
列0-8表示负重0-8的9个背包
（注最后一行3改成4）
如行号0，表示0号物体A,重4，只有在4号这个背包才能加入，后面背包5，6，7也只能加入4，8号背包可以加入两个A物体

行号1，加入物体B,重5，上一行的数保留，如果该行比上一行大则替换，
背包4保留，背包5放入B，背包6放入B，5700>4500替换

行号2，加入C，重2，背包2放入C，背包3可以放入B和背包1中的东西（此时背包1为0），到背包6，可以放入物体B，同时可以放入背包四中的东西（背包2+背包4=2250+4500=6750）后面以此类推

同时记录背包n最后加入的物体

如上表格：（1）背包8最后加入3号物体（D），重1
（2）8-1背包剩7，即到7号背包，七号背包最后加入2（C），重2
（3）7-2背包剩5，即到5号背包，五号背包最后加入1（B），重5
（4)5-5=0，剩余背包0

C代码

#include<stdio.h>
#include<stdlib.h>
#define LIMIT 8 //书包最大容量
#define N 5 //物品种类
#define MIN 1 //最小重量
struct Info
{
    char type[20];
    int weight;
    int price;
};
typedef struct Info myInfo;  //struct Info 用myInfo代替
int main()
{
    int item[LIMIT + 1] = { 0 };  
    int value[LIMIT + 1] = { 0 };
    int p,newvalue;
    myInfo my[] = { {"A",4,4500},{"B",5,5700},{"C",2,2250},{"D",1,1100},{"E",6,6700} };

    for (int i = 0; i < N; i++)
    {
        for (int j = my[i].weight; j <= LIMIT; j++)
        {
            p = j - my[i].weight;
            newvalue = my[i].price + value[p];
            if(newvalue > value[j])
            {
                value[j] = newvalue;
                item[j] = i;
            }
        }
    }
    printf("物品\t价格\n");
    for (int i = LIMIT; i >= MIN; i=i-my[item[i]].weight)
    {
        printf("%s\t%d\n", my[item[i]].type, my[item[i]].price);
    }
    printf("共\t%d\n", value[LIMIT]);
    system("pause");
}

python

# -*- coding: utf-8 -*-
""" Created on Mon Nov 13 11:41:38 2017 @author: yangwenbin """
N=5
LIMIT=9
MIN=1
myInfo=[0]*N
class Info():
    def __init__(self,Type,weight,price):
        self.Type=Type
        self.weight=weight
        self.price=price
        pass
    pass
myInfo[0]=Info('A',4,4500)
myInfo[1]=Info('B',5,5700)
myInfo[2]=Info('C',2,2250)
myInfo[3]=Info('D',1,1100)
myInfo[4]=Info('E',6,6700)
def backspace():
    value=[0]*LIMIT
    item=[0]*LIMIT
    for i in range(N):
        for j in range(myInfo[i].weight,LIMIT):
            p=j-myInfo[i].weight
            newvalue=myInfo[i].price+value[p]
            if newvalue>value[j]:
                value[j]=newvalue
                item[j]=i
                pass
            pass
        pass

    print("物品\t价格\n")
    i=LIMIT-1
    while i>=MIN:
        print("%c\t%d\n"%(myInfo[item[i]].Type,myInfo[item[i]].price))
        i=i-myInfo[item[i]].weight
    print(value[LIMIT-1])
if __name__=="__main__":
    backspace()