Acer C740, Acer C910, Acer CB5-571, Toshiba Chromebook 2 and Dell Chromebook 13, see here:Click

Flash Custom Coreboot BIOS

Warning: this BIOS is only for the Acer C720, C720P, HP Chromebook 14, Toshiba CB-30, and Dell Chromebook 11.

1. Please remove the write protect screw before flashing the BIOS.

2. Please check your CPU before flashing the BIOS.

3. Easy Flashing Script:
   cd ~; curl -L -O https://goo.gl/1hFfO3; sudo bash 1hFfO3

Select the “Install/Update custom coreboot firmware” option.

Create USB Installer

Use rufus to create the Windows 10 64 bit USB installer. Select MBR for legacy BIOS and create the USB drive.

You will need a USB keyboard/mouse for installation

Install Chipset, Audio, WiFi, and Bluetooth Drivers

Audio Driver: Link

Chipset Driver: Use the latest from Windows Update!

WiFi Driver: Use the latest from Windows Update!

Bluetooth Driver: Use the latest from Windows Update!

Run the setup files for the audio and chipset drivers. For WiFi and Bluetooth, use Device Manager to update the driver.

Turn on testsigning

Open Command Prompt as administrator, and type in “bcdedit /set testsigning on”. Then reboot.

Keyboard Driver

Download: Link

Open Device Manager and search for an unknown device that has a Hardware ID of either “ACPI\VEN_GGL&DEV_0303” or “ACPI\GGL0303”. Under the driver tab, click “Update Driver” and browse to the croskeyboard3 driver. Then install.

Trackpad Driver (Cypress Trackpad)

Download: Link

Open Device manager and search for an unknown device that has a Hardware ID of either “ACPI\VEN_CYAP&DEV_0000” or “ACPI\CYAP0000”. Under the driver tab, click “Update Driver” and browse to the crostrackpad3 driver. Then install.

Trackpad Driver (Elan Trackpad)

Download: Link

Open Device manager and search for an unknown device that has a Hardware ID of either “ACPI\VEN_ELAN&DEV_0000” or “ACPI\ELAN0000”. Under the driver tab, click “Update Driver” and browse to the crostrackpad3 driver. Then install.

Visual Studio 2015 Redistributable:

Download: Link

Trackpad Driver Helper Utilities (Cypress and Elan Trackpads)

Download: Link

Place the trackpad driver utility in the Windows startup folder (Start > Run > shell:startup) and run it after installing the driver.

Touch Screen Driver (Acer C720P users only)

Download: Link

Open Device manager and search for an unknown device that has a Hardware ID of either “ACPI\VEN_ATML&DEV_0001” or “ACPI\ATML0001”. Under the driver tab, click “Update Driver” and browse to the crostouchscreen2 driver. Then install.

Graphics Driver

Grab the latest Graphics Driver from Windows Update!

Embedded Controller Driver + Utility (Optional)

Download: Link

Visual Studio 2013 Redistr

ibutable: Download

If you like running Windows on your chromebook, please donate if you are able to do so. I have made these drivers and the BIOS available free of charge and am relying on donations to be able to get Windows running on more chromebooks (Pixel 2, Dell Chromebook 13).
For support, please see https://reddit.com/r/chrultrabook
Please donate here.

from : reddit.com chrultrabook

application software

Also referred to as apps. Software that can perform useful work, such as word processing, cost estimating, or accounting tasks. The user primarily interacts with application software.

Blu-ray

A type of high-definition disc with a capacity of 25 to 50 gigabytes.

cloud computing

Data stored at a server on the Internet and available anywhere the Internet can be accessed.

communication device

Computer systems that communicate with other computer systems using modems. For example, it modifies computer output into a form that can be transmitted across standard telephone lines.

compact disc (CD)

Widely used optical disc format. It holds 650 MB (megabytes) to 1 GB (gigabyte) of data on one side of the CD.

computer competency

Becoming proficient in computer-related skills.

connectivity

Capability of the microcomputer to use information from the world beyond one’s desk. Data and information can be sent over telephone or cable lines and through the air so that computers can talk to each other and share information.

data

Raw, unprocessed facts that are input to a computer system that will give compiled information when the computer processes those facts. Data is also defined as facts or observations about people, places, things, and events.

database file

File containing highly structured and organized data created by database management programs.

desktop computer

Computer small enough to fit on top of or along the side of a desk and yet too big to carry around.

device driver

Every device that is connected to the computer has a special program associated with it called a device driver that allows communication between the operating system and the device.

DVD (digital versatile disc or digital video disc)

Similar to CD-ROMs except that more data can be packed into the same amount of space. DVD drives can store a typical capacity of 4.7 GB on one side.

document file

File created by a word processor to save documents such as letters, research papers, and memos.

end user

Person who uses microcomputers or has access to larger computers.

flash memory card

A solid-state storage device widely used in notebook computers. Flash memory also is used in a variety of specialized input devices to capture and transfer data to desktop computers.

general-purpose application

Application used for doing common tasks, such as browsers and word processors, spreadsheets, databases, management systems, and presentation graphics. Also known as productivity applications.

handheld computer

See personal digital assistant (PDA).

hard disk

Enclosed disk drive containing one or more metallic disks. Hard disks use magnetic charges to record data and have large storage capacities and fast retrieval times.

hardware

Equipment that includes a keyboard, monitor, printer, the computer itself, and other devices that are controlled by software programming.

information

Data that has been processed by a computer system.

information system

Collection of hardware, software, people, data, and procedures that work together to provide information essential to running an organization.

information technology (IT)

Computer and communication technologies, such as communication links to the Internet, that provide help and understanding to the end user.

input device

Piece of equipment that translates data into a form a computer can process. The most common input devices are the keyboard and the mouse.

Internet

A huge computer network available to everyone with a microcomputer and a means to connect to it. It is the actual physical network made up of wires, cables, and satellites as opposed to the Web, which is the multimedia interface to resources available on the Internet.

keyboard

Input device that looks like a typewriter keyboard but has additional keys.

laptop computer

See notebook computer and notebook system unit.

mainframe computer

This computer can process several million program instructions per second. Sizeable organizations rely on these room-size systems to handle large programs and a great deal of data.

memory

Memory is contained on chips connected to the system board and is a holding area for data instructions and information (processed data waiting to be output to secondary storage). RAM, ROM, and CMOS are three types of memory chips.

microcomputer

Small, low-cost computer designed for individual users. These include desktop, notebook, and personal digital assistant computers.

microprocessor

The central processing unit (CPU) of a microcomputer controls and manipulates data to produce information. The microprocessor is contained on a single integrated circuit chip and is the brains of the system.

midrange computer

Also known as a minicomputer.

mobile app (application)

Add-on features for a variety of mobile devices, including smartphones, netbooks, and tablets.

modem

Short for modulator-demodulator. It is a communication device that translates the electronic signals from a computer into electronic signals that can travel over telephone lines.

monitor

Output device like a television screen that displays data processed by the computer.

mouse

Device that typically rolls on the desktop and directs the cursor on the display screen.

network

The arrangement in which various communications channels are connected through two or more computers. The largest network in the world is the Internet.

notebook computer

Portable computer, also known as a laptop computer, weighing between 4 and 10 pounds.

operating system (OS)

Software that interacts between application software and the computer, handling such details as running programs, storing and processing data, and coordinating all computer resources, including attached peripheral devices. It is the most important program on the computer. Windows 7, Windows Vista, and Mac OS X are examples of operating systems.

optical disc

Storage device that can hold over 17 gigabytes of data, which is an equivalent of several million typewritten pages. Lasers are used to record and read data on the disc. The two basic types of optical discs are compact discs (CDs) and digital versatile or video discs (DVDs).

output device

Equipment that translates processed information from the central processing unit into a form that can be understood by humans. The most common output devices are monitors and printers.

people

End users who use computers to make themselves more productive.

personal digital assistant (PDA)

A device that typically combines pen input, writing recognition, personal organizational tools, and communication capabilities in a very small package. Also called handheld PC and palm computer.

presentation file

A file created by presentation graphics programs to save presentation materials. For example, a file might contain audience handouts, speaker notes, and electronic slides.

printer

Device that produces printed paper output.

procedures

Rules or guidelines to follow when using hardware, software, and data.

program

Instructions for the computer to follow to process data. See software.

random-access memory (RAM)

Volatile, temporary storage that holds the program and data the CPU is presently processing. It is called temporary storage because its contents will be lost if electrical power to the computer is disrupted or the computer is turned off.

secondary storage

Permanent storage used to preserve programs and data that can be retained after the computer is turned off. These devices include floppy disks, hard disks, magnetic tape, CDs, DVDs, and more.

server

A host computer with a connection to the Internet that stores document files used to display web pages. Depending on the resources shared, it may be called a file server, printer server, communication server, web server, or database server.

smartphone

A type of cell phone that offers a variety of advanced functionality, including Internet and e-mail.

software

Computer program consisting of step-by-step instructions, directing the computer on each task it will perform.

solid-state drive (SSD)

Designed to be connected inside a microcomputer system the same way an internal hard disk would be, but contains solid-state memory instead of magnetic disks to store data.

solid-state storage

A secondary storage device that has no moving parts. Data is stored and retrieved electronically directly from these devices, much as they would be from conventional computer memory.

specialized application

Programs that are narrowly focused on specific disciplines and occupations. Some of the best known are multimedia, Web authoring, graphics, virtual reality, and artificial intelligence.

supercomputer

Fastest calculating device ever invented, processing billions of program instructions per second. Used by very large organizations like NASA.

system software

“Background” software that enables the application software to interact with the computer. System software consists of the operating system, utilities, device drivers, and language translators. It works with application software to handle the majority of technical details.

system unit

Part of a microcomputer that contains the CPU. Also known as the system cabinet or chassis, it is the container that houses most of the electronic components that make up the computer system.

tablet

A type of microcomputer that contains a thin system unit, most of which is the monitor. The best-known tablets are Apple’s iPad, Motorola’s Zoom, and HP’s Slate.

tablet computer

A type of notebook computer that accepts handwritten data, using a stylus or pen, that is converted to standard text and can be processed by a word processor program.

USB drive

The size of a key chain, these hard drives connect to a computer’s USB port enabling a transfer of files; has a capacity of up to 64GB.

utility

Performs specific tasks related to managing computer resources or files. Norton Utility for virus control and system maintenance is a good example of a utility. Also known as service programs.

virus

Hidden instructions that migrate through networks and operating systems and become embedded in different programs. They may be designed to destroy data or simply to display messages.

web

Introduced in 1992 and prior to the web, the Internet was all text. The Web made it possible to provide a multimedia interface that includes graphics, animations, sound, and video.

wireless revolution

A revolution that is expected to dramatically affect the way we communicate and use computer technology.

worksheet file

Created by electronic spreadsheets to analyze things like budgets and to predict sales.

如果只是想单纯的安装Arch Linux
请移步Arch Linux安装教程
完善的中文Wiki)

Arch Linux简介

Arch Linux(或称Arch)是一种以轻量简洁为设计理念的Linux发行版。
Arch Linux 将简洁定义为：避免任何不必要的添加、修改和复杂增加。它提供的软件都来自原始开发者(上游)，仅进行和发行版(下游)相关的最小修改。
Arch向GNU/Linux用户提供了许多新特性，包括systemd初始化系统、现代的文件系统（Ext2/3/4、Reiser、XFS、JFS、BTRFS）、LVM2/EVMS、软件磁盘阵列（软RAID）、udev支持、initcpio（附带mkinitcpio）以及最新的内核（目前是4.4）。

速度不错的国内镜像

基本系统安装

关于分区

本想使用GPT分区表，查了一些资料，为了使这个U盘在 BIOS 和 UEFI 电脑上都能用，需要创建一个BIOS boot分区，2M大小足够，位置尽量靠前。 多系统的话还要创建一个200M的 EFI System Partition(ESP)分区。但是有大神说GPT中的NTFS分区在Win7下不认（感觉Win8、Win10应该可以） 想用这个分区作为常规U盘使用就不行了，只好再回到MBR分区表。如果是移动硬盘用 GPT 应该没有问题。

所以仍然使用MBR分区，所以就要用fdisk或者cfdisk了，不能使用支持GPT的gdisk和cgdisk，4k对齐也是自动完成。
为了在安装过程中能更好认清我的分区，我先在Windows下用DiskGenius进行了分区，只可惜不支持ext4，之后再格式化一下就好。16G的U盘分区规划如下：

第一个分区 5G的ntfs分区，为了这个U盘还能进行一些拷拷文件的工作（非必须，看具体情况来吧)
第二个分区 100M的分区 /boot；
第三个分区 6G的分区，作为ArchLinux根分区；
第四个分区 4G的分区，作为 /home；

先刻录一个U盘启动盘吧

开始用ultraISO刻了几次都无法启动（原因是ultraISO不分青红皂白的写了syslinux引导进去），看来Arch真的是与众不同，于是用了烧录树莓派的Win32 Disk Image，成功。同理，在Linux下用dd命令应该也是可以的。
启动，进入Arch Linux安装界面，选择合适的版本，直接就进root了！这时可以插上你要安装的U盘。

分区

启动U盘是 /dev/sdb，目标U盘就成了 /dev/sdc。下面是在Linux显示的分区，并不是我的优盘，网上找来的,仅供参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# fdisk /dev/sdc

Disk /dev/sdc: 8022 MB, 8022982656 bytes, 15669888 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk label type: dos
Disk identifier: 0x00000000

Device Boot Start End Blocks Id System
/dev/sdc1 2048 1804287 901120 7 HPFS/NTFS/exFAT
/dev/sdc2 * 1804288 2009087 102400 83 Linux
/dev/sdc3 2009088 10405887 4198400 83 Linux
/dev/sdc4 10405888 15669887 2632000 83 Linux

在root下直接重新格式化为ext4

1
2
3
4

# mkfs.ntfs -f /dev/sdc1 -L f004-c
# mkfs.ext4 -b 4096 -m 0 -i 16384 -O '^has_journal' /dev/sdc2 -L f004-boot
# mkfs.ext4 -b 4096 -m 1 -i 16384 -O '^has_journal' /dev/sdc3 -L f004-a
# mkfs.ext4 -b 4096 -m 0 -i 16384 -O '^has_journal' /dev/sdc4 -L f004-b

-b 4096 是每个存储块的大小。 -m 1 是指定 root 保留空间为 1%，home 区就不留了。 -i 16384 是指定多少字节的数据设置一个 inode 节点， 增加它的值会减少 inode 的总数，占用的空间会少一些， 相应的能够存储的文件数量也减少了，这个稍微注意一下就好，一般都够用。 -O ‘^has_journal’ 是关掉文件系统日志，有点小危险。

挂载分区

1
2
3
4
5

# mount /dev/sdc3 /mnt      //没有根什么也挂不上啊
# mkdir /mnt/boot
# mount /dev/sdc2 /mnt/boot
# mkdir /mnt/home
# mount /dev/sdc4 /mnt/home

用df -h检查一下

1 2 3 4 5 6

//显示 # ext4 Filesystem Size Used Avail Use% Mounted on /dev/sdc3 5.9G 8.1M 6.0G 1% /mnt /dev/sdc2 96M 48K 96M 1% /mnt /dev/sdc4 3.8G 3.8M 3.9G 1% /mnt/home

基本系统安装

只讲一些必须的步骤

• 默认网络连接：
  dhcpcd（有线连接）

• 网络连接：
  无线连接：

  1	# wifi-menu

  ADSL 宽带连接：

  1 2	# pppoe-setup #配置 # systemctl start adsl #连接

pacman 软件仓库镜像服务器：

选择地理位置最为接近的镜像服务器以获得更高的下载速度。pacman优先使用位置靠前的镜像地址。将选定的镜像地址置于最前以便 pacman 使用。
注意：该配置不仅会应用到安装环境，也会应用至新系统中。

1

# nano /etc/pacman.d/mirrorlist

更新本地数据库：

1

# pacman -Syy

查看中国大陆的镜像服务器：

1

grep -A 1 'China' /etc/pacman.d/mirrorlist

选择所有的中国大陆的镜像服务器：

1

# sed -i '/Score/{/China/!{n;s/^/#/}}' /etc/pacman.d/mirrorlist

安装基础系统

1

# pacstrap -i /mnt base base-devel

提示共141个软件包，需要下载220.37M内容，安装完成后是 710.09M。

需要等待一会，休息一下

生成fstab

1

fstab： # genfstab -p -U /mnt >> /mnt/etc/fstab

然后更改fstab（系统默认一般就比较好了，不优化也行）。

下面的操作可以在 chroot 环境下运行

1

# arch-chroot /mnt

设置 hostname

1

echo 'nisuiyi' > /etc/hostname 。

设置时区

1

# ln -s /usr/share/zoneinfo/Asia/Shanghai /etc/localtime

新建 /etc/locale.conf 内容为

1
2
3

LANG='en_US.UTF-8'
LC_COLLATE='C'
LC_MESSAGES='C'

编辑 /etc/locale.gen

取消 en_US.UTF-8, zh_CN.UTF-8, zh_TW.UTF-8 前面的注释，然后执行 locale-gen 命令。

更改 root 密码

1

passwd root

安装 Grub 引导系统

仍然在chroot环境中操作。编辑 /etc/mkinitcpio.conf，检查HOOKS段，让 block 参数紧挨着 udev 参数之后（早一点加载），然后

1

# mkinitcpio -p linux

生成img文件。

使用pacman安装GRUB重要！

GRUB
BIOS：
安装:

1

# pacman -S grub os-prober

格式: grub-install –recheck /dev/<目标磁盘>,无论是32位还是64位系统，都是使用–target=i386-pc参数，–no-floppy是不检查软驱

1

# grub-install --target=i386-pc --recheck --boot-directory=/boot --no-floppy /dev/sdc

生成grub:

1
2

# grub-mkconfig -o /boot/grub/grub.cfg
# grep 'set=root' /boot/grub/grub.cfg

确保:

1

# blkid /dev/sdc2

UEFI：注意，仅UEFI使用这种方式

1
2
3

# pacman -S dosfstools grub efibootmgr
# grub-install --target=x86_64-efi --efi-directory=<EFI 分区挂载点> --bootloader-id=arch_grub --recheck
# grub-mkconfig -o /boot/grub/grub.cfg

退出收工

• 退出chroot，Ctrl + d 即可。

• umount

  1 2 3

  # umount /dev/sdc3 # umount /dev/sdc2 # umount /dev/sdc4

• 重启reboot

拔下启动U盘，用你的Arch Linux优盘启动吧。

贪心算法是我们在《计算机算法设计与分析》这门课中学习的几种重要的算法之一，顾名思义，贪心算法总是做出在当前看来最好的选择。也就是该算法并不从整体最优考虑，它所作出的选择只是在某种意义上的从局部的最优选择，寻找到解决问题的次优解的方法。虽然我们希望贪心算法得到的最终结果也是整体最优的，但是在某些情况下，该算法得到的只是问题的最优解的近似。

贪心算法思路

————问题通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。当达到算法中的某一步（不可简化的子问题）不能再继续前进时，算法停止。
该算法存在的短板：

1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
Begin 从问题的某一初始解出发；
while 能朝给定总目标前进一步
do 求出可行解的一个解元素；
end 由所有解元素组合成问题的一个可行解

背包问题描述

1. 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包（1）或不装入背包（0）。不能将物品i装入背包多次，也不能只装入部分的物品i。
2. 背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。背包问题可以定义如下：给出n个大小为w1,w2,…,wn,值为v1,v2,…,vn的项目，并设背包容量为C，要找到非负实数x1,x2,…,xn, 使和在约束下最大。

贪心算法解决背包问题有几种策略：

(i) 一种贪婪准则为：

从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], v =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。

(ii) 另一种方案是重量贪婪准则是：

从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], v=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。

(iii) 还有一种贪婪准则，就是我们教材上提到的：

认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], v=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<climits>
#include<cstring>

using namespace std;

float c = 10;    //背包容量
float w[] = {0,10,2,6,5,4};    //物品质量
float v[] = {0,6,3,5,4,6};    //物品价值
const int n = sizeof(w)/sizeof(w[0]) - 1 ;    //物品品种数
float x[n+1];    //背包中某种物品的质量（结果）

void Sort(int n,float v[],float w[])    //对物品的单位价值排序
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = i;j <= n;j++)
        {
            if(v[i]/w[i] < v[j]/w[j])
            {
                float tempv = v[i];
                v[i] = v[j];
                v[j]=tempv;

                float tempw = w[i];
                w[i] = w[j];
                w[j] = tempw;
            }
        }

    }
}

void printSort(int n,float v[],float w[])    //输出排序后结果
{
     for(int i = 1;i <= n;i++)
     {
        cout<<"v:"<<" "<<v[i]<<"    ";
        cout<<"w:"<<" "<<w[i]<<endl;
     }
}

void Knapsack(int n,float c,float v[],float w[],float x[])    //贪心选择
{
    Sort(n,v,w);
    int i;
    for(i = 1;i <= n;i++)
        x[i] = 0;
    //float c = M;
    for(i = 1;i <= n;i++)
    {
         if(w[i] > c)
             break;
         x[i] = 1;
         c-=w[i];
    }
    if(i <= n)
        x[i]= c/w[i];
}

int main()
{
    Knapsack(n,c,v,w,x);
    printSort(n,v,w);
    //输出结果
    cout << "The best answer is:\n";
    for(int j =1; j <= 5; j++)
    {
         cout << v[j] << " ";
    }
    cout << endl;
    for(int i = 1; i <= 5; i++)
        cout << x[i] * w[i] << " ";
    //system("pause");
    return 0;
}

问题描述：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装
入背包中物品的总价值最大?

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-11背包问题。

过程分析

数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6},
（第0位，置为0，不参与计算，只是便于与后面的下标进行统一，无特别用处，也可不这么处理。）总重量c=10.
背包的最大容量为10，那么在设置数组m大小时，可以设行列值为6和11，那么，对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<climits>
#include<cstring>

using namespace std;

const int c = 10;             //背包的容量
const int w[] = {0,2,2,6,5,4};//物品的重量，其中0号位置不使用 。
const int v[] = {0,6,3,5,4,6};//物品对应的待加，0号位置置为空。
const int n = sizeof(w)/sizeof(w[0]) - 1 ; //n为物品的个数
int x[n+1];

void package0_1(int m[][11],const int w[],const int v[],const int n)//n代表物品的个数
{
    //采用从底到顶的顺序来设置m[i][j]的值
    //首先放w[n]
    for(int j = 0; j <= c; j++)
        if(j < w[n]) m[n][j] = 0;     //j小于w[n],所对应的值设为0，否则就为可以放置
        else         m[n][j] = v[n];

    //对剩下的n-1个物品进行放置。
    int i;
    for(i = n-1; i >= 1; i--)
        for(int j = 0; j <= c; j++)
            if(j < w[i])
                m[i][j] = m[i+1][j];//如果j < w[i]则，当前位置就不能放置，它等于上一个位置的值。
    //否则，就比较到底是放置之后的值大，还是不放置的值大，选择其中较大者。
            else         m[i][j] = m[i+1][j] > m[i+1][j-w[i]] + v[i]?
                                       m[i+1][j] : m[i+1][j-w[i]] + v[i];
}
void answer(int m[][11],const int n)
{
    int j = c;
    int i;
    for(i = 1; i <= n-1; i++)
        if(m[i][j] == m[i+1][j]) x[i] = 0;
        else
        {
            x[i] = 1;
            j = j - w[i];
        }
    x[n] = m[i][j] ? 1 : 0;
}
int main()
{
    int m[6][11]= {0};

    package0_1(m,w,v,n);
    for(int i = 0; i <= 5; i++)
    {
        for(int j = 0; j <= 10; j++)
            printf("%2d ",m[i][j]);
        cout << endl;
    }
    answer(m,n);
    cout << "The best answer is:\n";
    for(int i = 1; i <= 5; i++)
        cout << x[i] << " ";
    system("pause");
    return 0;
}

原文链接